Hierarchical Navigable Small World (HNSW)

HNSW provides tunable precision-recall trade-offs via two key parameters: efConstruction and efSearch.

• efConstruction: Controls the dynamic candidate list size during graph building. A higher value creates a better-connected, more accurate graph but increases indexing time.
• efSearch: Controls the size of the dynamic candidate list during search. Increasing efSearch improves recall at the cost of slower query latency.
• This allows engineers to optimize for their specific SLA, whether it's sub-millisecond latency for real-time agents or >99% recall for batch analysis.

Unlike many ANN algorithms that require costly full rebuilds, HNSW supports efficient online insertions. New vectors are inserted by finding their nearest neighbors in each layer and establishing connections, without global reorganization. This is critical for agentic memory systems where knowledge is continuously accumulated. However, deletion is non-trivial and often handled via soft deletion markers, a consideration for systems requiring strict data removal.

Benchmarks consistently show HNSW outperforming other popular ANN algorithms on throughput-recall curves for medium to high-dimensional data (e.g., 100-1000 dimensions).

• Compared to IVF-PQ: HNSW typically achieves higher recall at equivalent speeds, though it uses more memory as it stores full-precision vectors.
• Compared to LSH (Locality-Sensitive Hashing): HNSW provides much higher accuracy for the same query time.
• Its performance is a key reason it is the default index in libraries like FAISS for high-accuracy scenarios and is widely implemented in vector databases (Weaviate, Qdrant, Milvus).

Memory Usage: HNSW's memory overhead is primarily the graph adjacency lists and the full-precision vectors. While heavier than compressed methods like PQ, it is often acceptable for in-memory indices up to hundreds of millions of vectors. Computational Cost: Search complexity is O(log N). Indexing (building the graph) is the most expensive phase, with complexity roughly O(N log N), but it is a one-time or batch cost. The algorithm is highly parallelizable during search, as multiple greedy traversals from different entry points can be explored.

A composite ANN algorithm that combines two techniques for high-efficiency search. It is a primary alternative to graph-based methods like HNSW.

• Inverted File (IVF): Partitions the vector space into Voronoi cells using k-means clustering, restricting search to a few promising clusters.
• Product Quantization (PQ): Compresses vectors by splitting them into subvectors and quantizing each separately, drastically reducing memory footprint. This method excels in memory-constrained environments and offers a different performance profile, favoring very high compression over the ultra-low latency of HNSW.

The core data structure within a vector store optimized for the rapid retrieval of vector embeddings. An HNSW graph is one type of embedding index. Design considerations include:

• Build Time vs. Query Time: Some indexes are slow to build but fast to query (like HNSW), while others build quickly.
• Memory vs. Disk: Indexes can be resident in RAM for speed or memory-mapped from disk for larger-than-memory datasets.
• Dynamic vs. Static: Support for incremental updates (adding/deleting vectors) without full rebuilds, a capability of HNSW.

The predominant metric used by HNSW and other vector search systems to measure semantic similarity between embeddings. It is defined as the cosine of the angle between two non-zero vectors.

• Calculation: For vectors A and B, similarity = (A · B) / (||A|| ||B||).
• Normalization: When vectors are L2-normalized (their Euclidean length is 1), cosine similarity simplifies to a dot product, which is computationally efficient.
• Range: Outputs a value between -1 and 1, where 1 indicates identical orientation, 0 indicates orthogonality, and -1 indicates opposite direction.