# MINT: Multi-Vector Search Index Tuning

arXiv: https://arxiv.org/abs/2504.20018 · HTML: https://mlsanity.com/paper/2504.20018/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 30 of its 90 references that are in the map.
- First posted on arXiv 28 Apr 2025.

## Builds on (most cited first, 30 of 30)

- [Learning Transferable Visual Models From Natural Language Supervision](https://mlsanity.com/paper/2103.00020/) (2021)
- [Billion-scale similarity search with GPUs](https://mlsanity.com/paper/1702.08734/) (2017)
- [ColBERT: Efficient and Effective Passage Search via Contextualized Late Interaction over BERT](https://mlsanity.com/paper/2004.12832/) (2020)
- [Multimodal Machine Learning: A Survey and Taxonomy](https://mlsanity.com/paper/1705.09406/) (2017)
- [Efficient and robust approximate nearest neighbor search using Hierarchical Navigable Small World graphs](https://mlsanity.com/paper/1603.09320/) (2016)
- [ColBERTv2: Effective and Efficient Retrieval via Lightweight Late Interaction](https://mlsanity.com/paper/2112.01488/) (2021)
- [The Faiss library](https://mlsanity.com/paper/2401.08281/) (2024)
- [Nomic Embed: Training a Reproducible Long Context Text Embedder](https://mlsanity.com/paper/2402.01613/) (2024)
- [Bridging Language and Items for Retrieval and Recommendation: Benchmarking LLMs as Semantic Encoders](https://mlsanity.com/paper/2403.03952/) (2024)
- [Embedding-based Retrieval in Facebook Search](https://mlsanity.com/paper/2006.11632/) (2020)
- [ANN-Benchmarks: A Benchmarking Tool for Approximate Nearest Neighbor Algorithms](https://mlsanity.com/paper/1807.05614/) (2018)
- [Fast Approximate Nearest Neighbor Search With The Navigating Spreading-out Graph](https://mlsanity.com/paper/1707.00143/) (2017)
- [A Comprehensive Survey and Experimental Comparison of Graph-Based Approximate Nearest Neighbor Search](https://mlsanity.com/paper/2101.12631/) (2021)
- [LatestEval: Addressing Data Contamination in Language Model Evaluation through Dynamic and Time-Sensitive Test Construction](https://mlsanity.com/paper/2312.12343/) (2023)
- [RaBitQ: Quantizing High-Dimensional Vectors with a Theoretical Error Bound for Approximate Nearest Neighbor Search](https://mlsanity.com/paper/2405.12497/) (2024)
- [Results of the NeurIPS'21 Challenge on Billion-Scale Approximate Nearest Neighbor Search](https://mlsanity.com/paper/2205.03763/) (2022)
- [Survey of Vector Database Management Systems](https://mlsanity.com/paper/2310.14021/) (2023)
- [When Large Language Models Meet Vector Databases: A Survey](https://mlsanity.com/paper/2402.01763/) (2024)
- [SPANN: Highly-efficient Billion-scale Approximate Nearest Neighbor Search](https://mlsanity.com/paper/2111.08566/) (2021)
- [Results of the Big ANN: NeurIPS'23 competition](https://mlsanity.com/paper/2409.17424/) (2024)
- [Practical and Asymptotically Optimal Quantization of High-Dimensional Vectors in Euclidean Space for Approximate Nearest Neighbor Search](https://mlsanity.com/paper/2409.09913/) (2024)
- [Worst-case Performance of Popular Approximate Nearest Neighbor Search Implementations: Guarantees and Limitations](https://mlsanity.com/paper/2310.19126/) (2023)
- [Manu: A Cloud Native Vector Database Management System](https://mlsanity.com/paper/2206.13843/) (2022)
- [WARP: An Efficient Engine for Multi-Vector Retrieval](https://mlsanity.com/paper/2501.17788/) (2025)
- [MUST: An Effective and Scalable Framework for Multimodal Search of Target Modality](https://mlsanity.com/paper/2312.06397/) (2023)
- [Subspace Collision: An Efficient and Accurate Framework for High-dimensional Approximate Nearest Neighbor Search](https://mlsanity.com/paper/2411.14754/) (2024)
- [DEG: Efficient Hybrid Vector Search Using the Dynamic Edge Navigation Graph](https://mlsanity.com/paper/2502.07343/) (2025)
- [What Looks Good with my Sofa: Multimodal Search Engine for Interior Design](https://mlsanity.com/paper/1707.06907/) (2017)
- [Retrieval with Learned Similarities](https://mlsanity.com/paper/2407.15462/) (2024)
- [Improved Space-Efficient Approximate Nearest Neighbor Search Using Function Inversion](https://mlsanity.com/paper/2407.02468/) (2024)

## Abstract (arXiv)

Vector search plays a crucial role in many real-world applications. In addition to single-vector search, multi-vector search becomes important for multi-modal and multi-feature scenarios today. In a multi-vector database, each row is an item, each column represents a feature of items, and each cell is a high-dimensional vector. In multi-vector databases, the choice of indexes can have a significant impact on performance. Although index tuning for relational databases has been extensively studied, index tuning for multi-vector search remains unclear and challenging. In this paper, we define multi-vector search index tuning and propose a framework to solve it. Specifically, given a multi-vector search workload, we develop algorithms to find indexes that minimize latency and meet storage and recall constraints. Compared to the baseline, our latency achieves 2.1X to 8.3X speedup.