Efficient Multivector Retrieval with Token-Aware Clustering and Hierarchical Indexing

Problem
This paper addresses the inefficiencies in multivector retrieval systems, particularly the computational and memory overhead associated with fine-grained token-level representations. Existing methods, primarily based on k-means clustering, struggle with scalability as they do not effectively represent rare, discriminative tokens and exhibit poor performance with large datasets and numerous clusters. The authors present TACHIOM, a novel approach that aims to enhance both clustering and retrieval efficiency while maintaining retrieval effectiveness. This work is a preprint and has not yet undergone peer review.

Method
TACHIOM introduces a token-aware clustering mechanism that optimizes centroid allocation based on token distribution, allowing for the management of millions of centroids. The architecture integrates a graph-based index over centroids with an optimized Product Quantization (PQ) layout, which facilitates efficient final scoring without the need for extensive token-level computations. The training process leverages a dataset that includes both MS-MARCOv1 and LoTTE, although specific training compute details are not disclosed. The method emphasizes the importance of token representation in clustering, ensuring that both frequent and rare tokens are adequately represented.

Results
TACHIOM demonstrates significant performance improvements over traditional k-means and state-of-the-art retrieval systems. Specifically, it achieves up to 247× faster clustering times compared to k-means and a retrieval speedup of up to 9.8× over existing systems. Effectiveness metrics remain comparable or superior, although specific numerical values for these metrics are not detailed in the summary. The benchmarks used for evaluation, MS-MARCOv1 and LoTTE, are well-regarded in the information retrieval community, providing a solid basis for the reported results.

Limitations
The authors acknowledge that while TACHIOM significantly improves clustering and retrieval speed, the reliance on token distribution for centroid allocation may introduce biases if the token distribution is not representative of the overall dataset. Additionally, the paper does not address the potential impact of varying document lengths or the effects of different tokenization strategies on performance. The scalability of TACHIOM in extremely large-scale applications or its performance in real-time retrieval scenarios remains unexamined.

Why it matters
The implications of TACHIOM are substantial for the field of information retrieval, particularly in applications requiring rapid response times and efficient resource utilization. By addressing the limitations of traditional clustering methods, TACHIOM paves the way for more scalable multivector retrieval systems that can handle large datasets with diverse token distributions. This work could influence future research on retrieval efficiency and the design of token-aware models, potentially leading to advancements in various applications such as search engines, recommendation systems, and natural language processing tasks.

Authors: Silvio Martinico, Franco Maria Nardini, Cosimo Rulli, Rossano Venturini
Source: arXiv:2604.28142
URL: https://arxiv.org/abs/2604.28142v1