HNSW Algorithm: The Secret Sauce Behind Lightning-Fast Vector Searches in RAG Systems 🔍⚡

Hello Hello Hello! 👋

Welcome back, everyone! We’ve journeyed through the RAG landscape together, exploring its foundations, components, and the unsung heroes of chunking and vector databases. Today, we’re diving into something super exciting — the HNSW algorithm (Hierarchical Navigable Small World) — the turbocharged engine that makes vector searches blazing fast! 🏎️💨

Remember when we talked about Vector Databases and mentioned those mysterious indexing algorithms like HNSW? Well, it’s time to pull back the curtain and see what makes this algorithm the secret weapon of modern RAG systems!

What is HNSW? 🤔

Remember when you are trying to find something, and start complaining that you are not able to find it, and then comes the most powerful search algorithm — “MOM”. And she’s able to find it instantly, then obviously you have to listen to some sweet comments 😂.

Now let’s take a similar example of a library, where you have thousands of books 📚, and you need to find that one book, let’s say “Designing Machine Learning Systems by Chip Huyen ” (It’s a great book by the way!)

Without any organization system, you’d have to check every single book — that would take forever! 🫠 This is what we call “brute force search” or “linear search” — basically, checking every item one by one.

What if instead:

1. You first look at a map that shows just the major sections (Computer Science, Machine Learning) — this basically represents the top layer in HNSW
2. Then narrow down to subsections (Machine Learning) — like moving to the middle layers
3. Finally zero in on the exact shelf with your required book! — reaching the ground layer with all the items

That’s essentially what HNSW does! It creates a hierarchical structure that lets you quickly navigate through your vector space, zooming from a high-level view down to exactly what you’re looking for.

But let’s get more technical! 🤓

HNSW stands for Hierarchical Navigable Small World, which builds upon the navigable small world concept. A “small world” in graph theory is a network where most nodes can be reached from every other node by a small number of steps. Ever heard of The “six degrees of separation” theory, it posits that everyone on Earth is connected to everyone else by a chain of no more than six social connections.

The hierarchy comes from organizing these small world graphs into multiple layers:

• Layer 0 (Ground Layer): Contains ALL data points with dense connections
• Higher Layers: Progressively contain fewer points with longer-range connections
• Each element’s maximum layer is chosen probabilistically based on an exponentially decaying distribution (don’t worry, that’s just fancy talk for “most elements stay in lower layers, few reach the top”)

This multi-layer architecture is what gives HNSW its logarithmic search complexity (𝑇(𝑛)=𝑂(𝑙𝑜𝑔(𝑛))) instead of the polylogarithmic complexity(𝑇(𝑛)=𝑂(𝑙𝑜𝑔(𝑛)^k)) of regular NSW.

Why Regular Graph Search Wasn’t Enough 😬

Before HNSW, we had the NSW (Navigable Small World) approach. It was good but had some serious limitations:

• Slow on Low-Dimensional Data: For simple data, NSW could be outperformed by basic tree algorithms by several orders of magnitude! 😱

-> Here’s why: NSW had what we call a polylogarithmic complexity scaling. This means if your dataset has N items, the search time grows with (log N)². For a 4-dimensional dataset, NSW could be 1000x slower than simple tree algorithms! (I know it’s a bit of an exaggeration but it’s true!)

1. The Polylogarithmic Problem: As your data grew, search times would increase with (log N)²

• This happens because both the number of steps AND the number of connections per node grow with dataset size
• Have you been to those restaurants where the waiter starts reciting all the menu items (Aloo parantha, gobhi parantha, pyaaz parantha, Masala Dosa….😋). Now imagine if the restaurant keeps increasing the menu items, now the waiter will take more time to recite all of those.

2. The Dreaded Local Minimum Trap: 🪤 NSW would often get trapped in “false local minimums” during its two-phase search:

• Zoom-out phase: Starting from a random node, searching neighbors until reaching an area similar in scale to your target
• Zoom-in phase: Refining the search in that local area
• The problem? Before reaching the target scale, the algorithm could get stuck in distant areas with low degree nodes — It’s similar to settling into a comfortable job position(SDE) that seems optimal in your current network, not realizing that much better opportunities(MLE) exist in adjacent industries you haven’t explored.

Similar to falling into a YouTube rabbit hole of DSA prep videos when you were actually looking for ML tutorials. NSW would often lead you far away from your actual search target!

How HNSW Works: The Magical Layers 🧙♂️

HNSW’s brilliance lies in its multi-layer structure. Let’s dive deep into how it works:

1. Layer Assignment: 📊 When inserting an element, we randomly decide its maximum layer using an exponential decay function:

• Formula: l = floor(-ln(uniform(0,1)) × mL) {Where mL is the normalization factor (typically 1/ln(M))}
• Let’s say for mL=1, most elements (~63%) end up only in layer 0, ~23% reach layer 1, ~8.5% reach layer 2 and so on….

• It’s like a social network where most people are regular users, some are influencers, and very few are celebrities! (Although it has changed, nowadays everyone seems to be a celebrity! 🫥)

2. Top-Down Search Strategy: 🔝 Unlike NSW which starts randomly, HNSW always begins from the top layer’s entry point:

• Think of it like a school hierarchy: The Principal oversees the heads of departments, who then manage teachers, and the teachers work directly with students.
• To reach a specific student (or data point), you start by asking the Principal, who guides you to the right department head, who sends you to the right teacher, and finally, you find the student.
• This top-down approach mirrors how HNSW navigates from the top layer down to finer layers for efficient search.

3. Greedy Navigation Algorithm: 🧭 At each layer, we perform a greedy search:

• Maintain a list of current best candidates
• Examine their neighbors to find even closer points
• When we can’t find anything closer, we’ve hit a local minimum
• The search is “greedy” because it always moves to the nearest neighbor without backtracking

4. Layer Transition Mechanics: ⬇️ When we hit a local minimum in layer L:

• We take our current best point as the entry point for layer L-1
• This point serves as an access point to the lower layers
• Each lower layer contains ~2–3x more nodes with shorter-range connections
• The search becomes more fine-grained, similar to zooming from a city map to a street map, This multi-resolution approach prevents getting trapped in distant false minima
• By progressively refining our search area, we efficiently narrow down to the exact target.

It’s like finding that “Designing Machine Learning Systems” book by first locating the Computer Science section, then the Machine Learning shelf, and finally scanning through the specific titles.

5. Final Search & Refinement: 🎯 On reaching layer 0:

• We perform a more thorough search with increased candidate set size, ef parameter(more on this later).
• We maintain a dynamic list of “ef” closest elements.
• This ensures we find the true nearest neighbors, not just approximate ones

Think of this whole process like navigating with Google Maps: You start with a country view (top layer), zoom to state level (mid layers), then street level (layer 0) for final navigation!

Visual Representation of HNSW Architecture 🎨

Here’s a simplified visual from the paper (Fig. 1) — see how the search starts from the top layer (red dot), then follows the red arrows, progressively refining the search as it moves down layers. Notice how each layer has progressively more nodes and shorter-range connections? That’s the hierarchical magic at work! 😎

The Smart Neighbor Selection Trick 🧠

One of the most ingenious parts of HNSW is how it chooses connections between nodes. Instead of just connecting to the nearest neighbors, it uses a clever heuristic! Let me break it down:

The Algorithm Behind the Magic 🪄

• Examine Candidates Sequentially: Start with the nearest candidate to your base element, then proceed to further one’s.
• Diversity Check: The key insight is that we DON’T simply pick the M nearest neighbors. Instead: We only connect to a candidate if it’s closer to the base element than ANY already connected neighbor –> This creates connections in diverse directions rather than just to nearby points

Why This is Brilliant 💡

This heuristic prevents a common problem in graph-based search: clustering causing disconnected components. Let me explain with an example:

Imagine you have two clusters of data (like two neighborhoods in a city):

• Without the heuristic: An element on the edge of Cluster 1 might only connect to other elements in Cluster 1, even if it’s technically closest to an element in Cluster 2. All its M connections get “used up” on nearby points in its own dense cluster.
• With the heuristic: It will form connections to both clusters because it prioritizes points in new directions. After connecting to a point in Cluster 1, other points in that same cluster likely won’t satisfy the “closer than ANY existing connection” criterion.

Think of it like networking at a conference:

• Bad approach: Only talk to people from your company (creating an echo chamber!)
• HNSW approach: Strategically connect with people from different companies, industries, and backgrounds (building diverse bridges)

Mathematical Properties 🧮

This heuristic approximates the construction of a relative neighborhood graph — a minimal subgraph of the Delaunay graph that maintains global connectivity while using only distance information between nodes.

I know I know, Now what the halua(a sweet dish in india!) is Delaunay?? 👇

What are Delaunay graphs? In simple terms, a Delaunay graph connects points in such a way that if you were to do a greedy search (always moving to the closest neighbor), you’d always reach the nearest neighbor of your query. It’s the ideal graph structure for nearest neighbor search, but unfortunately, it’s very difficult to construct efficiently in high dimensions.

The Skip List Connection: For 1D data, this heuristic produces an exact Delaunay subgraph (Basically in 1D in simple terms a Delaunay graph has a very simple structure: each point connects to its immediate left and right neighbors. So if you have points at positions [1, 5, 8, 12, 15], the connections would be: 1↔5, 5↔8, 8↔12, 12↔15), making HNSW equivalent to a probabilistic skip list in the 1D case!

What’s a skip list? It’s a data structure that allows fast search within an ordered sequence by maintaining multiple layers of linked lists:

• The bottom layer contains all elements in sorted order
• Higher layers act as “express lanes” with progressively fewer elements
• Elements in higher layers are chosen probabilistically
• Search starts at the top layer and drops down when it can’t move forward

Skip lists are used in many high-performance systems like Redis (for sorted sets) and Lucene (for term dictionaries). HNSW essentially generalizes this elegant 1D structure to work in any number of dimensions! ✨

Key Parameters That Make or Break HNSW 🔧

If you’re implementing HNSW, pay attention to these critical parameters:

1. M: Number of connections per element per layer

• Range: 5–48 (memory increases linearly with M)
• Lower M (5–12): Better for low dimensional data (d<10)
• Higher M (16–48): Essential for high dimensional data (d>100)
• Each value of M creates a different trade-off between memory, construction time, and search performance

2. efConstruction: Dynamic candidate list size during construction

• Range: Usually between 100–500
• Higher values create better connected graphs but take longer to build
• Rule of thumb: Start with 100, increase if recall is low
• Directly impacts the index quality (you’re basically running K-ANNS during construction!)

3. ef: Search-time dynamic candidate list size

• Range: k (number of neighbors you want)
• Higher ef = better accuracy but slower search
• Common strategy: Start with ef=40, double until desired recall
• This is your runtime accuracy knob!

4. mL: Level generation normalization factor

• Optimal value: 1/ln(M)
• Controls the distribution of nodes across layers
• Too high: Too many layers, overhead
• Too low: Inadequate separation, loses hierarchy benefits

5. Mmax0: Maximum connections on ground layer

• Usually set to 2×M
• Critical for high-recall searches
• Setting this equal to M can cause severe performance degradation at high recall

It’s like perfecting a recipe for Kadhai Paneer- get the spice balance just right, and you’ll have a masterpiece! 🍛 But unlike cooking, you can actually adjust these parameters with mathematical precision to find your perfect balance between memory usage, search speed, and accuracy based on your specific needs.

Real-World Performance: Mind = Blown 🤯

Let me throw some numbers at you! In tests on a 200M SIFT dataset:

• HNSW could achieve 90–95% recall in just ~1ms per query
• Competing algorithms(FAISS) needed around 20x more time for the same recall (and it didn’t even touch more than ~82% recall)
• Even with billions of vectors, HNSW maintains sub-millisecond query times

When to Use HNSW in Your RAG System 🛠️

HNSW is your go-to choice when:

1. You need blazing-fast search on large vector datasets
2. You’re working with high-dimensional data (like embeddings from language models)
3. You need to handle complex, clustered data structures
4. Memory isn’t your primary constraint (HNSW uses more memory than some other methods)

Some excellent libraries that have HNSW built-in:

• Qdrant: A vector database with HNSW as its primary index
• FAISS: Facebook’s library for efficient similarity search
• Milvus: An open-source vector database with HNSW support
• Annoy: Spotify’s approximate nearest neighbors library
• nmslib/hnswlib: The original implementation from the algorithm’s creators

Wrapping It Up 🎁

HNSW is truly the backbone that makes modern vector search blazing fast. When you’re chatting with your RAG-powered application and getting instant, relevant responses, there’s a good chance HNSW is working its magic behind the scenes!

Want to see HNSW in action with real code examples and performance benchmarks? Will be releasing a Kaggle notebook soon!

Till then, Happy Learning! Cheers! 🙌