PaperlayerView exact revision on arXiv

Source-linked AI summary

Lossless Compression of Proximity Graph Indexes for Efficient Approximate Nearest Neighbors Search

Francesco Benocci, Leonard Dahlmann, Francesco Gargiulo, Tobias Heuer, Silvio Martinico, Franco Maria Nardini, Cosimo Rulli, Rossano Venturini

arXiv:2610.37176v1cs.IR

TL;DR

Graph adjacency lists are a growing memory concern in ANN indexes, yet they must be decoded during online search without adding retrieval latency. The paper permutes graph nodes to induce locality, then compresses reordered, delta-encoded neighbor sequences with Stream VByte for fast SIMD decoding. Across datasets, it reports strong compression with zero to negligible latency penalties, and eBay deployment reduces graph storage without measurable latency degradation.

  • Problem

    Graph adjacency lists are a significant ANN memory target, but online search must decode them during query execution, making compression without added latency a challenge.

    Source: §1 · pp. 1–2

  • Method

    The framework permutes nodes to induce structural locality, then compresses reordered, delta-encoded neighbor sequences with Stream VByte in adjacency-list-aligned blocks for SIMD decoding.

    Source: §2.3 · p. 3, §5 · p. 7

  • Results

    Across all datasets, Stream VByte provides the best operating point, with compression ratio up to 2.1× and zero to negligible latency penalties versus the uncompressed baseline.

    Source: §5 · p. 7

  • Takeaways & Limitations

    In eBay production, the framework reduced HNSW graph storage by 44.3% at identical ANN recall, with no measurable latency degradation under live workloads.

    Source: §1 · p. 2

    The evaluation restricts analysis to low-degree HNSW configurations, where adjacency lists are shorter and per-list decompression cost is more pronounced.

    Source: §3.1 · p. 4

Abstract

from arXiv · show

Graph-based Approximate Nearest Neighbor (ANN) indexes, such as HNSW, are the backbone of modern vector search. However, their massive memory footprint creates a severe infrastructure bottleneck. While vector quantization is widely adopted to reduce the memory required to store data vectors, the graph's edge structure increasingly dominates total memory usage. Compressing these adjacency lists for online search presents a critical system challenge: because decompression occurs during query processing, i.e., while navigating the graph, memory savings cannot come at the expense of query latency. In this paper, we present a compression technique explicitly tailored for live HNSW routing. By applying offline graph permutations to artificially induce structural locality, we enable the use of SIMD-accelerated integer compressors, such as Stream VByte, for rapid on-the-fly decompression. Evaluated across diverse real-world workloads, we significantly outperform the current state of the art in both compression ratio and query latency. Our experimental results show that we achieve compression ratios up to 52.7% with negligible penalties in latency compared to the uncompressed baseline. Furthermore, our technique has been effectively deployed in production at eBay, achieving up to 44.3% reduction in edge storage with no degradation in query latency.

1 Introduction

Graph adjacency lists are an increasingly important memory target for ANN indexes, but decoding them during online search makes latency-preserving compression challenging. This work combines offline node permutation with Stream VByte and evaluates the approach across diverse workloads, including production deployment at eBay.

1 Introduction

  • Graph compression matters because graph structure can account for a large share of ANN index memory, particularly when vector representations are compact.ANN indexes commonly reside in main memory to support low-latency queries.Source: §1 · p. 1
  • The paper addresses a gap in in-depth study of graph compression, where adjacency lists must be decoded during queries and added decompression overhead affects retrieval latency.The study focuses on HNSW, a widely adopted graph-based ANN index.Source: §1 · p. 2
  • Offline node permutations improve adjacency-list compressibility, while Stream VByte provides negligible query-time decompression overhead through byte alignment and SIMD decoding.The benchmark suite covers classical and neural datasets, dense and sparse vectors, Euclidean distance and inner-product similarity, and datasets from 1M to approximately 9M vectors.Source: §1 · p. 2
  • 44.3% smaller HNSW graph at identical ANN recall, with no measurable latency degradation under eBay live workloads.The framework is deployed in Cassini and lets eBay extend HNSW to more search use cases.Source: §1 · p. 2
  • The framework reduces edge space by up to 52% on Sift1M, keeps latency within a few percent of the uncompressed baseline, and reaches up to 11% lower latency on eBayProducts7M at 98% Accuracy@10.The evaluation spans three public datasets and a private eBay products dataset.Source: §1 · p. 2
  • The authors plan to release a public implementation within the kANNolo Rust library.The implementation is described as planned for release.Source: §1 · p. 2

2 Background and Related Work

ANN methods trade exactness for faster retrieval, and HNSW uses a multi-level proximity graph to navigate toward query neighbors. For online graph compression, sorted and gap-encoded adjacency lists can be paired with fast integer decoding, while graph permutations induce locality that makes gaps smaller.

2.1 ANN Search

  • ANN search trades small accuracy losses for efficiency because exact nearest-neighbor search becomes computationally prohibitive as dataset size and dimensionality grow.The background also notes that high-dimensional kd-trees can degrade toward linear scan.Source: §2.1 · p. 2
  • HNSW uses higher, sparser graph levels for long-range navigation and the ground level, containing all points, to refine query results.Its parameters regulate node connections, construction candidates, and query exploration breadth.Source: §2.1 · p. 2

2.2 Graph Compression

  • Sorting adjacency lists permits integer encoding, and gap encoding stores differences between consecutive IDs to shift values toward smaller integers.The supplied passages describe this as a way to reduce sequence entropy.Source: §2.2 · pp. 2–3
  • Bit-by-bit entropy coding can provide strong compression but incurs latency, motivating byte- or word-aligned integer compressors for latency-sensitive pipelines.Traditional variable-byte decoding also has data-dependent branches that limit SIMD utilization.Source: §2.2 · p. 3
  • Stream VByte separates control and data streams for branch-free decoding, with block indexing that supports partial decoding and skipping.This layout fits queries that access only a subset of a graph's neighbors.Source: §2.2 · p. 3
  • List-reference compression exploits shared outgoing links in web graphs, but its applicability to proximity graphs remains unexplored in the cited discussion because online routing imposes distinct topology and latency requirements.Prior ANN work highlights the tension between compression effectiveness and online decoding costs.Source: §2.2 · p. 3

2.3 Graph Permutations

  • Graph permutations reorder vertex IDs to induce structural locality, since ingestion order often does not align with graph topology and can mask adjacency-list redundancy.The minimum linear arrangement formulation is NP-hard, so practical pipelines use partitioning heuristics; KaMinPar supports many-block partitioning for fine-grained ID grouping.Source: §2.3 · pp. 3–4
  • Recursive bipartitioning repeatedly splits balanced partitions, while direct k-way methods partition into k blocks; the cited literature reports advantages for direct methods in partition quality and execution speed.The passage identifies Metis, PaToH, and Scotch as recursive methods and KaMinPar as a scalable multilevel scheme.Source: §2.3 · pp. 3–4

3 Methodology

The methodology analyzes HNSW structure to guide compression choices, then combines offline node reordering, gap encoding, and fast integer compression for online routing.

3.1 Preliminary Analysis

  • Graph edges form a substantial share of HNSW index memory, especially for quantized or low-dimensional data, while degree caps leave short lists and little overlap.The evaluated CoCondenser and eBayProducts7M graphs concentrate near the 64-edge cap, with many nodes saturating it.Source: §3.1 · p. 4, Figure 1 · p. 4
  • 8.8% was the ideal aggregate space-saving ceiling for reference copying on eBayProducts7M, so the authors excluded it from further evaluation.The optimal reference yielded a net saving of 101 bits per list; practical reference-chain access would add latency.Source: §3.1 · p. 5
  • 18.69 bits on CoCondenser and 18.52 bits on eBayProducts7M were the gap-entropy values after direct gap encoding, down from 22.77 and 22.62 bits.The remaining gaps still span a large fraction of the ID space, while bit-packing exceeds zero-order entropy by at most 1.23 bits per value.Source: §3.1 · p. 5, Figure 3 · p. 5
  • 14.99 bits on eBayProducts7M and 16.02 bits on CoCondenser were the post-EGB gap entropies; KaMinPar reduced them further to 14.90 and 15.86 bits.Reordering concentrates edge density along the diagonal, so graph-adjacent nodes increasingly receive nearby IDs.Source: §3.1 · p. 5, Figure 4 · p. 5, Figure 3 · p. 5
  • Stream VByte sacrifices less than 1 bit per edge relative to Zeta while enabling branch-free SIMD decoding, making it the selected codec for latency-sensitive routing.The comparison uses EGB-permuted gap lists; Zeta has the smallest practical footprint among the universal codes surveyed.Source: §3.1 · p. 6, Figure 5 · p. 6

3.2 Implementing our Compression Framework

  • The final pipeline applies EGB, gap-encodes adjacency lists, compresses them with Stream VByte, and uses Elias–Fano for the offset array.Per-list decoding supports on-demand neighborhood expansion; the abstraction leaves HNSW search unchanged and buffers decoded neighbors in stack-allocated chunks.Source: §3.1 · p. 6, §3.2 · p. 6

4 Experiments

Experiments compare edge-compression methods across four image, text, and product-embedding workloads, measuring memory footprint, search effectiveness, and latency. Stream VByte provides the best overall operating point, while graph permutation adds an offline build cost.

4 Experiments

  • The four benchmarks span SIFT image descriptors, dense SnowFlake text, sparse CoCondenser text, and eBay product embeddings.The SnowFlake MsMarco encoding exceeds 30 GB and is compressed with PQ at 32× storage reduction, followed by reranking with uncompressed representations.Source: §4 · p. 6
  • Stream VByte combines strong compression with efficient decoding across four benchmarks; its query latency matches or improves on Plain for three and adds only marginal overhead on Sift1M.Its memory footprint is within roughly 4–10% of Zeta’s.Source: Table 2 · p. 7, §4 · p. 7
  • Methods are evaluated by bits per edge, Accuracy@10, and average query latency, with latency reported for the fastest configuration reaching each accuracy cutoff.The cutoffs are 90%, 94%, and 98%.Source: §4 · p. 7, Table 2 · p. 7
  • Zeta has the smallest memory footprint, reducing it 1.7×–2.3× versus Plain, but slows queries by up to ≈27% on Sift1M and ≈14% on eBayProducts7M.Bitpacker reduces memory 1.3×–1.6× while keeping latency close to Plain; Elias–Fano is consistently slowest and compresses no better than Bitpacker.Source: §4 · p. 7
  • Permutation accounts for 3.5% of total build time on CoCondenser, 7.8% on SnowFlake, 15% on eBayProducts7M, and 30% on Sift1M.The passage characterizes index construction as a one-time offline procedure.Source: §4 · p. 7

5 Conclusions and Future Work

The framework permutes graph nodes offline to induce locality, then compresses reordered, delta-encoded neighbor sequences with Stream VByte for fast SIMD decoding. It achieves up to 2.1× compression with zero-to-negligible latency penalties on public benchmarks and reduces eBay’s HNSW graph memory by 44.3% without measurable query-latency degradation; future work would extend and co-design compression.

5 Conclusions and Future Work

  • Offline node permutation induces structural locality that lowers adjacency-list entropy under gap encoding, after which adjacency-list-aligned Stream VByte blocks support fast SIMD decoding.The evaluation covers four benchmarks spanning image, dense and sparse text, and product embeddings.Source: §5 · p. 7
  • Compression reaches 2.1× with zero-to-negligible latency penalties on public benchmarks; in eBay production, HNSW graph memory falls 44.3% with no measurable query-latency degradation.Source: §5 · p. 7
  • Future work would extend the framework to Vamana or NSG and co-design graph and vector compression in a unified index.The proposed co-design targets regimes where edges and vectors contribute comparably to index size.Source: §5 · p. 7

GenAI Usage Disclosure

The authors disclose using generative AI tools for language editing and code assistance, with subsequent review and editing by the authors.

GenAI Usage Disclosure

Related papers

Loading 2610.37176v1…