Comprimere i grafi HNSW senza rallentarli

Vector search is often powered by proximity graphs such as HNSW (Hierarchical Navigable Small World)¹. The edges of these graphs can take a large part of the index memory, especially when the vectors are short or quantized (compressed). In our latest work in collaboration with eBay (CIKM 2026), Lossless Compression of Proximity Graph Indexes for Efficient Approximate Nearest Neighbors Search², we show how to compress the adjacency lists of HNSW by up to 2.1× without slowing down search. The technique has been running in production at eBay since early 2025, where it reduces the memory taken by the edges by 44.3%, and it is now also available in kANNolo³.

Where the memory goes

HNSW limits the number of neighbors of each node. In our graphs a node has between 30 and 50 neighbors on average, and each of them is stored as a 32-bit ID. When the vectors themselves are small, these IDs end up taking a large share of the index. On some datasets, such as eBay's short product embeddings or the MS MARCO-v1⁴ passages encoded with Snowflake⁵ and quantized with Product Quantization (PQ)⁶, the edges take more than half of the memory:

However, compressing the edges must not slow down search. A graph traversal visits the nodes in an unpredictable order, so each adjacency list has to be decoded on the fly while the search is running, and the decoding time adds directly to the query time.

Making IDs compressible

We evaluated several approaches, including WebGraph⁷, the well-known framework for compressing web graphs, which encodes a list as a copy of a similar list plus a few extra edges. None of them works well on HNSW graphs, because two adjacency lists usually share very few neighbors. For this reason, we compress each list independently.

The usual way to do this is to sort the list and store the gaps between consecutive IDs. However, node IDs follow the insertion order and have nothing to do with the structure of the graph, so the neighbors of a node are spread over the whole ID space. On eBayProducts7M, bit-packing costs 23 bits per ID and the entropy of the IDs is 22.6 bits, which means that they are close to uniform. Storing gaps instead of IDs only brings the entropy down to 18.5 bits.

To fix this, we renumber the nodes so that nodes appearing in the same lists get close IDs. The permutation is computed offline with Enhanced Graph Bisection (EGB)⁸, a recursive bisection algorithm designed for reordering indexes. After EGB, the entropy of the gaps on eBayProducts7M drops to 15.0 bits.

The vectors are permuted together with the nodes, so the search runs entirely in the new ID space and only the final results are mapped back to the original IDs. Storing the inverse permutation needed for this mapping costs ⌈log₂ N⌉ bits per vector. Reordering also improves cache locality⁹: on eBayProducts7M, it alone makes the uncompressed index 17% faster.

Choosing the codec

We compared several integer codecs on the reordered gaps (the plot above counts the adjacency lists alone, without the offsets and the inverse permutation). Zeta codes¹⁰ come closest to the entropy. Stream VByte¹¹ uses about one bit more per edge, but it is byte-aligned and stores the byte lengths of four integers in a separate control byte, so it can be decoded with SIMD (Single Instruction, Multiple Data) instructions and without branches. Since each adjacency list is encoded independently, the search only decodes the lists of the nodes it actually visits.

The offsets that mark where each list starts are compressed with Elias-Fano¹². They take about 8 bits per node instead of 64, and any offset can still be accessed directly.

Results

We report results on two datasets: eBayProducts7M, a collection of 7.3M 96-dimensional product embeddings from eBay, and MS MARCO-v1 encoded with Snowflake. The Snowflake vectors are compressed with PQ, and the retrieved candidates are reranked on the full vectors with a RerankIndex¹³. The paper also reports results on Sift1M and on MS MARCO-v1 encoded with the sparse CoCondenser¹⁴ model.

The plot below shows the space taken by each method in bits per edge, including the offsets and, for the reordered graphs, the inverse permutation. Under each value is the compression ratio with respect to the uncompressed graph (Plain):

The table reports the average query latency in µs at 90 / 94 / 98% Accuracy@10:

Zeta compresses the most, but it is 13–16% slower than Plain on eBayProducts7M and 6–10% slower on MS MARCO-v1 Snowflake. Elias-Fano is the slowest method and does not compress better than bit-packing. Stream VByte takes only about one bit per edge more than Zeta and is as fast as Plain or faster. On eBayProducts7M it is even 11% faster at 98% accuracy, thanks to the better locality of the reordered graph. The other two datasets in the paper show the same trend, with only a small overhead on Sift1M.

Computing the permutation adds 7.8% (MS MARCO-v1 Snowflake) and 15% (eBayProducts7M) to the build time, and it is a one-time offline cost.

In production at eBay

eBay's search engine, Cassini¹⁵, uses HNSW for vector retrieval. This compression framework has been part of its production pipeline since early 2025. The process is the same as the one described above, except that the permutation is computed with KaMinPar¹⁶, a k-way graph partitioner, instead of EGB. At identical recall, the edges of the HNSW graph take 44.3% less memory, with no measurable latency degradation under live traffic. The memory saved allows eBay to use HNSW in more search use cases.

Try it in kANNolo

Graph compression is a single argument on every HNSW index in kANNolo (pip install kannolo). Search results are identical to those of the uncompressed index, and IDs are the original ones:

import numpy as np
from kannolo import DensePlainHNSW
 
data = np.load("embeddings.npy").astype(np.float32)  # shape (n, 1024)
query = data[0]
 
index = DensePlainHNSW.build_from_array(
    data.flatten(), dim=1024,
    m=32, ef_construction=200, metric="dotproduct",
    graph_type="compressed",  # EGB permutation + Stream VByte
)
index.save("index.bin")
 
# The file does not record the graph type, so pass it again when loading.
index = DensePlainHNSW.load("index.bin", metric="dotproduct", graph_type="compressed")
dists, ids = index.search(query, k=10, ef_search=100)

graph_type="permuted" applies only the reordering, for faster queries without the space savings. The same option is available on the sparse and PQ indexes and in the hnsw_build binary (--graph-type streamvbyte). The graph compression guide has the details, and the code to reproduce the paper is in our reproducibility repository.