HNSW graph compression cuts storage with little latency cost
Lossless Compression of Proximity Graph Indexes for Efficient Approximate Nearest Neighbors Search · arXiv:2610.37176
In plain words
Vector search finds items whose number-based descriptions are close to a query. A hierarchical navigable small world (HNSW) index also stores links between nearby items, and those links can use substantial memory.
The paper introduces a lossless way to store HNSW links in less space while still unpacking them during search. In tests on four datasets, search latency stayed near the uncompressed version at the same retrieval accuracy, while the links used less storage.
The research
In a vector search index, graph links can take substantial memory, especially when vectors are stored compactly. It remains unclear whether those links can be compressed while still letting an online search unpack visited neighborhoods without costly delay.
For hierarchical navigable small world (HNSW) indexes, the authors reorder node IDs and losslessly encode neighbor lists for fast, on-demand search.
In four varied dataset tests, the authors compare Stream VByte compressed graphs with Plain, their uncompressed HNSW version. They measure edge storage and average query latency at matched retrieval-accuracy targets.
Storage falls by up to 2.1 times on Sift1M. Across the datasets, latency matches or improves on the uncompressed version for three and is only marginally higher for Sift1M, supporting a storage gain with little measured latency cost in these tests.
These results support a storage and latency trade-off for the tested HNSW settings, not every graph index or workload. The search parameters were tuned to reach each accuracy target, and the paper does not establish that they were identical between compressed and uncompressed runs.
What the evidence shows
- The storage and speed trade-off
The lossless HNSW adjacency-list compression framework is a method for reducing the memory used by links in a hierarchical navigable small world (HNSW) index. It addresses a trade-off: graph links can occupy substantial memory, especially with compact vectors, but search must unpack visited neighborhoods, and that decoding work can add latency. The question is whether the links can take less space without making retrieval slower.
- Why list copying was rejected
The authors first test whether lists can save space by referring to shared neighbors in other lists. Even an idealized calculation, which ignores reference-ID costs and permits unlimited cyclic chains, gives a ceiling of only 8.8% of edge space on eBayProducts7M.
Since a practical version would save less and add delay when following references, they set this approach aside and instead try to make individual lists more compressible.
- Reordering makes gaps smaller
Their next step is to reorder graph node IDs so connected nodes tend to have nearby IDs, then store the differences between neighbor IDs. On eBayProducts7M, the global entropy is 22.62 bits per value for original edge IDs, 18.52 after ordinary gap encoding, and 14.99 for gaps after EGB reordering.
This measurement across all adjacency-list values shows how reordering makes the gaps more compressible; it does not alone show how fast search will be.
- Testing storage and latency
The authors compare Stream VByte compressed graphs with Plain, the uncompressed version, on four datasets. Accuracy@10 measures the share of the true ten nearest neighbors found among the ten results, averaged over queries; they compare average latency at matched accuracy targets.
Stream VByte cuts edge storage by up to 2.1 times on Sift1M, while its latency is close to Plain across the datasets, supporting a storage gain with little measured latency cost in these tests.
- Evidence from production
The paper gives a separate production result from eBay’s live HNSW search system: graph storage fell by 44.3% at identical approximate-nearest-neighbor recall, with no measurable latency degradation under live workloads.
This supports the framework’s usefulness in that specific system. Together, the dataset tests and production report show reduced storage with little measured latency cost in their stated settings, while the paper leaves results on other graph-index families open.
Deep
- Original paper authors
- Francesco Benocci, Leonard Dahlmann, Francesco Gargiulo, Tobias Heuer, Silvio Martinico
- Submitted to arXiv
- License
- CC BY 4.0