EUVIMEDScopri EUVIMED
Crossref

GEM: A Native Graph-based Index for Multi-Vector Retrieval

Yao Tian, Zhoujin Tian, Xi Zhao, Ruiyuan Zhang, Xiaofang Zhou

Proceedings of the ACM on Management of Data · 2026-05-18 · 4 (3) · 1-27

DOI: 10.1145/3802065 ↗

At a glance

Journal article in Proceedings of the ACM on Management of Data, published online on 2026-05-18. Written by Yao Tian and 4 co-authors. 66 references. Funded by: Hong Kong Research Grants Council, HKUST-WeBank Joint Laboratory, HKUST-MetaXJoint Laboratory for Advanced AI Computing.

AbstractDati bibliograficiCiteRelated studies

Abstract (original language)

In multi-vector retrieval, both queries and data are represented as sets of high-dimensional vectors, enabling finer-grained semantic matching and improving retrieval quality over single-vector approaches. However, its practical adoption is held back by the lack of effective indexing algorithms. Existing work, attempting to reuse standard single-vector indexes, often fails to preserve multi-vector semantics or remains slow. In this work, we present GEM, a native indexing framework for multi-vector representations. The core idea is to construct a proximity graph directly over vector sets, preserving their fine-grained semantics while enabling efficient navigation. First, GEM designs a set-level clustering scheme. It associates each vector set with only its most informative clusters, effectively reducing redundancy without hurting semantic coverage. Then, it builds local proximity graphs within clusters and bridges them into a globally navigable structure. To handle the non-metric nature of multi-vector similarity, GEM decouples the graph construction metric from the final relevance score and injects semantic shortcuts to guide efficient navigation toward relevant regions. At query time, GEM launches beam search from multiple entry points and prunes paths early using cluster cues. To further enhance efficiency, a quantized distance estimation technique is used for both indexing and search. Across in-domain, out-of-domain, and multi-modal benchmarks, GEM achieves up to 16× speedup over state-of-the-art methods while matching or improving accuracy.

Funding

  • Hong Kong Research Grants Council
  • HKUST-WeBank Joint Laboratory
  • HKUST-MetaXJoint Laboratory for Advanced AI Computing

Cite

APA

Tian, Y., Tian, Z., Zhao, X., Zhang, R., & Zhou, X. (2026). GEM: A Native Graph-based Index for Multi-Vector Retrieval. Proceedings of the ACM on Management of Data, 4(3), 1-27. https://doi.org/10.1145/3802065

Vancouver

Tian Y, Tian Z, Zhao X, Zhang R, Zhou X. GEM: A Native Graph-based Index for Multi-Vector Retrieval. Proceedings of the ACM on Management of Data. 2026;4(3):1-27. doi:10.1145/3802065

BibTeX
@article{Tian2026,
  author = {Tian, Yao and Tian, Zhoujin and Zhao, Xi and Zhang, Ruiyuan and Zhou, Xiaofang},
  title = {GEM: A Native Graph-based Index for Multi-Vector Retrieval},
  journal = {Proceedings of the ACM on Management of Data},
  year = {2026},
  volume = {4},
  number = {3},
  pages = {1--27},
  doi = {10.1145/3802065}
}
Start for free →