Hierarchical Navigable Small World Graphs: The Key to Unlocking Embedding Search

Introduction

Advances in deep learning and the proliferation of large pre-trained models have made embeddings a fundamental data type in modern AI systems. Text, images, videos, and more can all be encoded as dense vectors in a high-dimensional space, such that semantically similar items have embedding vectors that are close to each other. This enables a powerful paradigm of searching and retrieving relevant information based on the similarity of embeddings rather than exact matches.

However, performing similarity search on embeddings introduces significant challenges compared to traditional lookup methods. Embeddings typically have hundreds or thousands of dimensions, making them unsuitable for conventional index structures designed for low-dimensional data. Naively comparing a query embedding against an entire database is prohibitively slow for large-scale applications.

This is where approximate nearest neighbor (ANN) search algorithms come in. ANN methods trade off some accuracy for greatly improved speed by searching only a subset of a database and returning close neighbors rather than the exact closest ones. Within the family of ANN algorithms, graph-based approaches have emerged as some of the most successful, and in particular, hierarchical navigable small world (HNSW) graphs.

In this post, we will dive deep into the HNSW algorithm, exploring why it has become the backbone powering embedding search in many state-of-the-art AI and database systems. We‘ll explain the core ideas behind HNSW, analyze its strengths and weaknesses, and highlight its real-world applications. By the end, you will see why HNSW is a key component in the quest to organize and retrieve the world‘s information to build intelligent systems.

The Embedding Search Problem

First, let‘s formalize the problem HNSW is designed to solve. We have a database of 𝑁 items, each represented by a 𝐷-dimensional embedding vector. Given a query vector 𝒒, our goal is to find the 𝑘 nearest neighbors of 𝒒 in the database according to some distance metric like Euclidean distance or cosine similarity. We denote this 𝑘-NN set as 𝑁𝑘(𝒒).

The naive solution is to exhaustively compare 𝒒 against every vector in the database, which takes Θ(𝑁𝐷) time. This quickly becomes intractable for large 𝑁 and 𝐷. For example, finding the top 10 neighbors in a database of 1 million 512-dim embeddings would require 512 million distance computations!

ANN search relaxes the problem by finding an approximate 𝑘-NN set 𝑁′𝑘(𝒒) rather than the exact one. The quality of the approximation is typically quantified by recall@k, defined as:

recall@k = |𝑁𝑘(𝒒) ∩ 𝑁′𝑘(𝒒)| / 𝑘

Achieving high recall with much lower query time than exhaustive search is the key challenge.

Navigating a Hierarchy of Small Worlds

The HNSW algorithm builds on a powerful intuition: a hierarchical graph structure can efficiently encode the similarity relations in an embedding dataset across multiple scales.

At the foundation is the idea of navigable small world (NSW) graphs. A NSW graph has two key properties. First, the graph has a high clustering coefficient, meaning that nodes tend to form tightly connected local neighborhoods with their most similar neighbors. Second, the graph has a low effective diameter due to a small number of shortcut long-range edges that connect distant regions.

The "small world" property enables a simple greedy search strategy to find approximate nearest neighbors: start at a random node and recursively move to the neighbor closest to the query until no closer nodes are found. With high probability, only a small fraction of the nodes need to be explored to find a good approximation.

However, NSW search can fail on large datasets with intricate local structure. The greedy algorithm may get trapped in a suboptimal region and fail to explore more distant parts of the graph. Even with shortcut edges, the graph diameter may be too large relative to the size of the dataset.

HNSW addresses these issues by building a hierarchy of NSW graphs. Each level 𝑙 is an NSW graph containing a subset of 𝑀𝑙 nodes selected from the level below, with 𝑀0 = 𝑁 being the original dataset. The graph density decays exponentially up the hierarchy, with 𝑀𝑙 = 𝑀𝑙−1/𝛼 for some constant 𝛼 > 1.

Hierarchy Construction

HNSW constructs the hierarchy incrementally by inserting nodes one at a time. The insertion algorithm follows a two-phase approach of first finding the nearest neighbors at all levels using a graph traversal, followed by updating each level‘s graph.

To insert a new node 𝑞 at the base level:

1. Perform a greedy search from a random entry point to find 𝑞‘s 𝑀0 nearest neighbors.
2. Designate 𝑞‘s nearest neighbor 𝑒𝑝 as the entry point for the next level.
3. Connect 𝑞 to its 𝑀0-closest neighbors, ensuring the connections are mutual.

This process is repeated at each level until reaching the top, with two key differences:

1. The number of neighbors 𝑀𝑙 decreases exponentially with the level.
2. The probability of 𝑞 being selected for insertion at a higher level decreases exponentially with the level.

The end result is a hierarchy of NSW graphs where each level is an increasingly coarse approximation of the original dataset, but with drastically reduced density. Edges represent the approximate nearest neighbor relations at each scale.

ANN Search

To perform an ANN query, HNSW conducts a multi-scale graph traversal:

1. Start at the top level 𝐿 and perform a greedy search to find the closest node 𝑒𝑝𝐿.
2. Use 𝑒𝑝𝐿 as the entry point for a greedy search at level 𝐿-1 to find 𝑒𝑝𝐿−1.
3. Repeat step 2 until reaching 𝑒𝑝0 at the base level.
4. Perform a final greedy search at the base level starting from 𝑒𝑝0 to find the 𝑘-NN.

This hierarchical search strategy allows HNSW to quickly narrow down the search space from the entire dataset to a small local neighborhood with only a few jumps. Most of the graph remains unexplored, while still finding high-quality nearest neighbors.

Benchmarks and Applications

HNSW has proven to be one of the most effective ANN algorithms across a range of benchmarks and real-world use cases.

On standard ANN benchmarks like SIFT1M and GIST1M, HNSW dominates most other algorithms in the recall-vs-speedup tradeoff. For example, on SIFT1M (1 million 128-dim vectors), HNSW achieves a recall@1=0.97 while being 1000x faster than exhaustive search. The closest competitors (FLANN, Annoy, FALCONN, etc.) are either significantly slower or have much worse recall.

HNSW‘s exceptional performance has made it the backbone of many industry-strength systems for embedding search:

• Microsoft uses HNSW in their SPTAG library for vector search in Azure cloud services.
• Alibaba‘s PASE hybrid search engine uses HNSW for product image retrieval and recommendations.
• Facebook has published extensions of HNSW for non-Euclidean embedding spaces like Poincaré disk models.
• Pinecone, Weaviate, Faiss, ScaNN, and other vector databases use HNSW under the hood.

As a concrete example, consider natural language search over large documents. By embedding paragraphs, pages, or entire documents using a language model, we can precompute an HNSW index to enable fast retrieval based on the similarity to an input query. When the query is a question, this powers question-answering via retrieval of the most relevant passages likely to contain the answer.

This retrieval-augmented generation paradigm combining ANN search with large language models has become a core component of systems like OpenAI‘s ChatGPT, DeepMind‘s Retro, Anthropic‘s Claude, and Meta‘s Atlas. HNSW‘s speed and scalability make it a common choice to implement the vector search functionality.

HNSW in the Past, Present, and Future of AI

I‘ve always been fascinated by how the pursuit of intelligence seems to inevitably lead us to confront the fundamental challenge of search – searching through vast possibility spaces to discover the knowledge and skills needed to navigate the world. With the rise of deep learning, that world is increasingly represented by high-dimensional vector embeddings capturing the semantics of language, vision, and other modalities in a form amenable to learning and reasoning.

While the large language models and neural nets tend to get the most attention, I believe the unsung heroes are the ANN algorithms like HNSW that empower these models to interface with vast knowledge bases necessary for open-ended intelligence. Indeed, I would argue that a large model without effective ANN search is akin to a brain without sensory inputs connecting it to the environment.

Looking ahead, I‘m excited about several frontiers that could expand the reach and power of HNSW and its conceptual relatives:

• Learning-based indexes that adapt the graph structure to the query distribution and embeddings for even greater efficiency and robustness, e.g., SONG.
• Distributed graph embedding and querying methods for web-scale datasets, e.g., CLEAR.
• Integration with non-neural techniques like inverted indexes and dual encoders for semantic search over structured and unstructured data.
• Retrieval from multimodal (text, images, etc.) representations and knowledge graphs.
• Hardware acceleration and compression techniques to reduce latency and increase throughput.

Zooming out, I believe we‘re witnessing a Cambrian explosion of innovation at the intersection of AI, databases, and information retrieval. HNSW is an instructive example of how a relatively simple idea – extending small world graphs to a multi-scale hierarchy – can have an outsized impact when combined with the right domain insights and engineering.

To create the next generation of intelligent systems, we will need many more such insights to efficiently index and navigate the ever-expanding universe of vector representations. But with techniques like HNSW lighting the way, the future looks bright indeed.