GEM: A Native Graph-based Index for Multi-Vector Retrieval
Proceedings of the ACM on Management of Data · 18.05.2026 · 4 (3) · 1-27
DOI: 10.1145/3802065 ↗Kurz gefasst
Fachartikel in der Zeitschrift Proceedings of the ACM on Management of Data, online erschienen am 18.05.2026. Verfasst von Yao Tian und 4 weiteren Autor:innen. Die Arbeit nennt 66 Literaturangaben. Gefördert von: Hong Kong Research Grants Council, HKUST-WeBank Joint Laboratory, HKUST-MetaXJoint Laboratory for Advanced AI Computing.
Abstract (Originalsprache)
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.
Förderung
- Hong Kong Research Grants Council
- HKUST-WeBank Joint Laboratory
- HKUST-MetaXJoint Laboratory for Advanced AI Computing
Zitieren
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}
}
EUVIMED