Lossless Compression of Proximity Graph Indexes for Efficient Approximate Nearest Neighbors Search: what it means for business leaders

A team from ISTI-CNR, the University of Pisa and eBay shows that relabelling an HNSW graph offline and encoding its neighbour lists with Stream VByte roughly halves edge memory with no measurable query latency cost, and eBay runs it in production.

1. What the method is

The advance is a lossless compression scheme for the adjacency lists of HNSW proximity graphs that decompresses during search with no measurable latency penalty. The authors first relabel the graph's nodes offline with a partitioning heuristic, Enhanced Graph Bisection, so that nodes which appear together in neighbour lists receive numerically close identifiers. Each sorted list is then stored as gaps between consecutive identifiers, the gaps are encoded with Stream VByte, a byte-aligned integer codec that decodes with SIMD instructions, and the per-node offset array is compressed with Elias-Fano. The dataset vectors are permuted together with the node identifiers, so search runs entirely in the relabelled space and only final results are mapped back. On four benchmarks the scheme cuts edge storage from about 33 bits per edge to between 16 and 19, a reduction of 1.7 to 2.1 times, and it has been in production in eBay's search engine Cassini since early 2025.

2. Why the method was developed

Graph indexes such as HNSW dominate vector search because they balance recall and latency well, but they are built to live entirely in memory, and memory is what runs out first at scale. Vector quantization is widely used to shrink the vectors, and the better it works the more the remaining footprint is the graph itself: on the product-quantized SnowFlake index and on eBay's low-dimensional product embeddings the edges, not the vectors, are the dominant cost. Compressing edges is harder than compressing vectors because every neighbour list must be decoded on the fly while a query walks the graph, so decoding overhead lands directly on latency. Earlier lossless work from Meta settled on bit-packing and Elias-Fano for this online case, which save roughly a quarter to a third of the space; entropy coders save more but decode bit by bit, too slowly for live routing. Web-graph reference compressors do not apply because HNSW caps node degree, so lists barely overlap: the authors bound the ideal saving at 8.8 percent.

3. Who should care

This touches anyone who runs or pays for vector search in production. Platform and search infrastructure teams operating HNSW indexes in Elasticsearch, Qdrant, Weaviate, Pinecone, FAISS or a home-grown engine get the direct benefit: the same index on roughly half the edge memory, which means fewer or smaller nodes, or more collections and use cases on the same fleet, which is exactly what eBay reports. Finance and capacity planning should note the change in the cost curve, since memory is the binding constraint for these systems and the saving scales linearly with corpus size. ML and retrieval engineers choosing quantization levels gain room, because edge compression composes with vector compression rather than competing with it. Vendors of vector databases should expect this to become a standard feature; buyers of such databases can ask whether graph storage is compressed and what it costs at query time.

4. How the method works

HNSW stores, for every vector, a sorted list of neighbour identifiers, capped at 64 per node in these graphs. Default identifiers follow ingestion order and carry no structure, so bit-packing is already within a fraction of a bit of the zero-order entropy, and plain gap encoding only lowers the per-value cost from about 22.7 to 18.6 bits. The gain comes from the permutation: Enhanced Graph Bisection clusters the graph into densely connected regions and assigns consecutive identifiers inside each, which pulls the edge mass onto the diagonal and drops the gap entropy to 16.0 bits on CoCondenser and 15.0 on the eBay graph. The gaps are then encoded one list at a time with Stream VByte, which keeps a separate control stream giving the byte length of four integers at once, so the decoder is branch-free and decodes a single neighbourhood on demand into a stack buffer. Offsets into the flat edge array sit in Elias-Fano, which supports the random access traversal needs. Reordering also improves cache locality, which alone cut uncompressed query time by 3 to 17 percent, at the price of storing an inverse permutation in bit-packed form.

5. How it was evaluated

We have the full paper, so the evaluation is reported in detail. The framework and all baselines were implemented inside the kANNolo Rust library, a tightly optimised uncompressed HNSW, so any overhead measured is genuine rather than masked by a slow baseline. Four datasets were used: Sift1M, one million image descriptors under Euclidean distance; two encodings of the 8.8 million MS MARCO passages under inner product, a dense SnowFlake embedding compressed with product quantization and reranked from uncompressed vectors, and a sparse CoCondenser encoding over the BERT vocabulary; and eBay's private set of 7.3 million product embeddings with real query traffic. Graph sizes range from 30 million to 400 million edges. Baselines are the uncompressed index, bit-packing, Elias-Fano and the Zeta universal code. Memory is measured in bits per edge including offsets and the inverse permutation; speed is the average microseconds per query of the fastest configuration reaching 90, 94 and 98 percent Accuracy@10, on an Intel Xeon Silver 4314.

6. How it performed

Stream VByte gave the best operating point on every dataset. Edge storage fell from 33.4 to 19.4 bits per edge on CoCondenser, 33.3 to 18.3 on eBay products, 34.1 to 16.1 on Sift1M and 33.6 to 18.0 on SnowFlake, ratios of 1.7 to 2.1, within about one bit per edge of Zeta, the most compact codec. Latency at 98 percent accuracy was 765 microseconds against 778 uncompressed on CoCondenser, 564 against 632 on eBay products, an 11 percent speed-up, 494 against 497 on SnowFlake, and 114 against 111 on Sift1M, the one small penalty. Zeta paid for its extra compression with slowdowns of roughly a quarter on Sift1M; Elias-Fano was slowest and compressed no better than bit-packing. Permutation adds 3.5 to 30 percent to one-time build time. The abstract's headline ratio and the eBay deployment figure did not survive the rendering we have, beyond the statement that eBay sees a smaller graph at identical recall with no measurable latency change. Limits: HNSW only, low-degree graphs, and edges only, not vectors. Our call: pilot it on our largest HNSW index once the kANNolo release lands, and ask our vector database vendor for the equivalent. (Source: arXiv 2610.37176, 2026)