hnsw | Hasty Briefs

<antirez>

2 months ago

The author took a break from HNSW development to write a blog post sharing advanced findings, especially on making HNSWs fast enough for a low-latency, high-performance system like Redis.
The original HNSW paper lacks key details like deletion support and the necessity of multiple layers; the author modified HNSW to support actual removal of entries and questions if the 'H' (hierarchical) aspect is always beneficial.
Memory scaling is addressed by using 8-bit quantization per vector (computing max absolute value) which gives ~4x speedup, 4x reduction in vector size, and almost no recall loss; full precision and binary quantization options are also available.
For speed, threads are used for reads and partial writes; a per-node epoch array prevents revisiting visited nodes during concurrent searches, and writes split into a reading-half and commit-half to minimize lock contention.
To reclaim memory on deletion, links are forced to be bidirectional, and a distance matrix is computed among neighbors of a deleted node to reconnect them greedily, preserving graph quality.
HNSWs are exposed as a Redis data structure (Vector Sets) with commands VADD, VREM, VSIM, allowing composability across keys/instances and per-user/per-item indexing; this also simplifies scaling by hashing elements modulo N.
Loading time is accelerated by serializing the entire graph structure (nodes and neighbor pointers) so that rebuilding is allocation only, achieving a 100x speedup; security checks ensure validity even with corrupted RDB files.
A JSON filter mechanism allows mixed search (e.g., vector similarity plus metadata constraints) within the greedy search loop, letting users specify effort and filter by JSON attributes.
In-memory HNSWs are acceptable for many use cases (e.g., 3M Word2Vec entries take 3GB RAM); the author believes HNSWs will remain relevant and encourages further research.