Hierarchical Navigable Small World (HNSW) is an approximate nearest-neighbor (ANN) indexing algorithm for finding vectors close to a query vector. Embedding models represent items such as documents, images, and products as numerical vectors. A vector search compares these representations using a measure such as Euclidean distance, cosine distance, or inner product. A brute-force exact search evaluates every eligible vector; HNSW instead explores a graph to find promising candidates, typically performing far fewer comparisons. Other exact-search algorithms can prune candidates while preserving correctness, so exhaustive scanning is not a requirement of exact search itself.
The index contains several graph layers. The bottom layer includes all indexed vectors, while progressively higher layers contain smaller subsets selected through randomized level assignment. Search begins in an upper layer, navigating toward nodes closer to the query, and then descends through lower layers. Sparse upper layers provide long-range navigation; the larger bottom layer supports more detailed candidate exploration. The hierarchy describes the search structure, not a business taxonomy or a hierarchy of document categories.
In a cloud application, an ingestion pipeline generates embeddings and writes them alongside identifiers and metadata into a vector-capable data store. That store builds and maintains an HNSW index. For example, a support assistant can embed a user's question, retrieve nearby document chunks, and pass those chunks to a language model. HNSW performs retrieval; it neither generates embeddings nor produces the final answer. Stored and query vectors must use compatible embedding models, dimensions, and preprocessing, and the index must support the intended similarity measure.
Three common tuning controls govern the main trade-offs, although names and availability differ by implementation. M controls graph connectivity: larger values generally increase memory consumption and construction work but can improve recall. ef_construction controls candidate exploration during index construction, affecting build cost and graph quality. ef_search controls candidate exploration during queries; increasing it generally improves recall at the cost of additional latency and CPU work. The requested result count, k, is distinct from the search exploration budget.
HNSW often provides high recall and low latency, but it does not guarantee the exact nearest neighbors. Measure recall@k against an exact-search baseline using representative queries, then evaluate latency percentiles, throughput, index size, and ingestion performance. Graph links add storage overhead beyond the vectors themselves. Traditional implementations can be memory-intensive, although some systems support disk-backed or compressed variants. Incremental insertion is supported, but update, deletion, cleanup, and rebuild behavior depend on the implementation.
For data-store selection, distinguish HNSW from inverted file (IVF) indexes. IVF partitions vector space into clusters and searches selected partitions rather than traversing a multilayer graph. Common IVF implementations require training representative centroids, whereas HNSW does not require a separate centroid-training phase. HNSW often suits high-recall, low-latency retrieval when sufficient resources are available. IVF offers different memory and performance trade-offs, particularly when combined with compression. Neither index family is universally faster or more accurate; benchmark both against the workload when both are available.
Metadata filtering is another practical consideration. A tenant or access-control filter can change how many useful candidates a search finds, especially if filtering occurs after approximate retrieval. Verify the store's filtering behavior and test highly selective predicates; requesting ten neighbors does not always produce ten qualifying results, even when enough matching records exist. Choose the data store using the complete workload, including SQL or keyword-search requirements, consistency, filtering, ingestion rate, resource costs, and supported index controls—not simply the presence of an HNSW option.
Amazon OpenSearch Service