HNSW
Hierarchical Navigable Small World - a graph-based approximate nearest neighbor index algorithm used in OpenSearch for fast k-NN vector search. HNSW indexes enable millisecond retrieval across millions of embeddings by navigating a multi-layer proximity graph rather than scanning all vectors.
HNSW is the indexing algorithm behind the memory gateway's vector search capability. It constructs a multi-layer graph where each node (memory embedding) is connected to its nearest neighbors, and higher layers provide long-range shortcuts for fast traversal. At query time, HNSW navigates from a random entry point, following edges toward the query vector with a greedy search strategy, achieving approximate nearest-neighbor results in O(log n) time rather than the O(n) of brute-force search. In the tiered storage architecture, HNSW indexing is reserved for the hot tier - recent, high-trust memories that need millisecond retrieval. The warm tier uses standard OpenSearch indexing without HNSW acceleration, and the cold tier relies on object storage with no live index. The ef_search parameter controls the accuracy-speed tradeoff: higher values explore more candidates and produce more accurate results at the cost of latency.