HNSWLib is a header-only C++ library that implements the Hierarchical Navigable Small World (HNSW) algorithm for approximate nearest neighbor search. The library is designed to find items similar to a query item in large collections of vector data without comparing the query against every item individually. It is commonly used in Machine learning systems, Artificial intelligence applications, and vector databases where speed and scalability are critical.
The HNSW algorithm, which HNSWLib implements, stores vectors in a multi-layer graph structure. Each vector becomes a node, and links connect it to nearby vectors. Upper layers contain fewer nodes and act as a coarse map, while the bottom layer contains all nodes for detailed searching. A search begins in an upper layer, follows links toward nodes closer to the query, then repeats the process in lower layers until it identifies a set of likely nearest neighbors.
Background
The nearest neighbor search problem asks which items in a dataset are closest to a query item. A direct search compares the query with every item, which becomes slow for large datasets. Exact methods using spatial trees like the k-d tree or R-tree lose effectiveness in high-dimensional data due to the curse of dimensionality. Approximate nearest neighbor methods trade exactness for speed, returning close items quickly rather than guaranteeing the absolute closest.
HNSW builds on research into small-world networks and navigable graphs. In small-world graphs, most nodes connect through short chains of links. Jon Kleinberg's work on navigation in small-world networks influenced later research on adding links that make graphs easier to navigate greedily. The HNSW algorithm extends earlier navigable small world methods by adding a hierarchy of graph layers, which helps find a good region before detailed searching.
Algorithm
HNSWLib uses a proximity graph where nearby vectors are connected by edges. The algorithm moves through the dataset using these edges rather than scanning every vector. The graph is hierarchical: every vector appears in the bottom layer, while some vectors also appear in higher layers with fewer vectors as layers ascend. Upper layers enable long-range movement, while lower layers allow detailed search near promising candidates.
A typical search starts from an entry point in the highest layer. At each step, the algorithm examines neighboring nodes and moves to one closer to the query. When no closer neighbor exists in that layer, it descends to the next layer. In the bottom layer, it explores a wider candidate set and returns the nearest candidates found. This greedy navigation repeatedly chooses locally better nodes to approach the query point.
Construction and parameters
The HNSW graph is built incrementally. When inserting a new vector, the algorithm assigns it a maximum layer, searches for nearby existing nodes, and connects the new node to selected neighbors in each layer where it appears. Implementations expose parameters controlling trade-offs between speed, accuracy, memory use, and construction time. Higher graph connections improve recall but require more memory. Larger search candidate lists improve accuracy but slow queries. Larger construction candidate lists improve graph quality but slow index building.
Because HNSW is approximate, results may differ from exact searches. Practical performance depends on dataset characteristics, distance measure, implementation quality, and parameter settings. Benchmarking studies have found HNSW-based libraries to be strong performers among approximate nearest neighbor methods, though worst-case performance can differ from common benchmark results.
Use in vector search systems
HNSWLib is used as an index in systems storing and searching high-dimensional vectors, including vector databases, search engines, and database extensions. Typical applications include semantic search, recommender systems, image similarity search, and retrieval-augmented generation. The library is associated with the original HNSW authors and is widely adopted in production environments.
Several software projects implement or support HNSW. Libraries include HNSWLib and FAISS. Database and search systems documenting HNSW support include Apache Lucene, Chroma, ClickHouse, DuckDB, MariaDB, Milvus, pgvector, Qdrant, and Redis. These systems leverage HNSW for fast approximate search in applications ranging from Large language model retrieval to Generative AI pipelines.
See also
- Approximate nearest neighbor search
- Vector database
- Locality-sensitive hashing
- Product quantization