Course contentsShow
← Machine Learning and Deep Learning
Lesson 1963 of 3,53842. Retrieval-Augmented Generation: FoundationsFree lesson

HNSW: Hierarchical Navigable Small World Graphs

Understanding the HNSW algorithm for efficient approximate nearest neighbor search.

HNSW: Hierarchical Navigable Small World Graphs

You'll learn how HNSW organizes vectors into a multi-layer graph structure to enable lightning-fast approximate nearest neighbor search.

The Core Idea

HNSW is one of the most popular algorithms for approximate nearest neighbor (ANN) search in vector databases. While you know ANN search avoids checking every vector by using clever data structures, HNSW specifically builds a multi-layer graph where vectors are nodes connected by edges to their nearby neighbors.

Think of it like a highway system: the top layers are express highways connecting distant cities (sparse, long-distance connections), while bottom layers are local roads connecting every neighborhood (dense, short-distance connections). When searching, you start on the highway to quickly get close to your destination, then exit to progressively more detailed roads until you reach the exact neighborhood.

How HNSW Works

Construction: Vectors are inserted into multiple layers probabilistically. Each vector appears in layer 0 (the bottom), but only some appear in layer 1, fewer in layer 2, and so on. At each layer, nodes maintain connections to their nearest neighbors at that scale.

Search: Start at the topmost layer with a random entry point. Greedily navigate to the closest node in that layer. When you can't get closer, drop down one layer and repeat. Eventually, you reach layer 0 with a very close starting point, then perform a final local search to find the k-nearest neighbors.

This hierarchical structure is what makes HNSW achieve sub-linear search time—you avoid exploring irrelevant regions entirely.

Key Takeaway: HNSW builds a multi-layer graph of vectors where upper layers enable coarse navigation and lower layers refine results, delivering fast approximate nearest neighbor search with excellent recall-speed tradeoffs for RAG retrieval systems.