Dense retrieval techniques utilize large pre-trained language models to construct a high-dimensional representation of queries and passages. These representations assess the relevance of a passage concerning a query through eficient similarity measures. Multi-vector representations, while enhancing efectiveness, cause a one-order-of-magnitude increase in memory footprint and query latency by encoding queries and documents on a per-token level. The current state-of-the-art approach, namely PLAID, has introduced a centroid-based term representation to mitigate the memory impact of multi-vector systems. By employing a centroid interaction mechanism, PLAID filters out non-relevant documents, reducing the cost of subsequent ranking stages. This paper 1 introduces "Eficient Multi-Vector dense retrieval with Bit vectors" (EMVB), a novel framework for eficient query processing in multi-vector dense retrieval. Firstly, EMVB utilizes an optimized bit vector pre-filtering step for passages, enhancing eficiency. Secondly, the computation of centroid interaction occurs column-wise, leveraging SIMD instructions to reduce latency. Thirdly, EMVB incorporates Product Quantization (PQ) to decrease the memory footprint of storing vector representations while facilitating fast late interaction. Lastly, a per-document term filtering method is introduced, further improving the eficiency of the final step. Experiments conducted on MS MARCO and LoTTE demonstrate that EMVB achieves up to a 2.8× speed improvement while reducing the memory footprint by 1.8× , without compromising retrieval accuracy compared to PLAID.
The widely acknowledged capability of Large Language Models (LLMs) to model semantic and
context has been extensively used in Information Retrieval. In Dense Retrieval, LLMs are used
to encode documents and queries into -dimensional vectors. This enables the modeling of
document-query relevance using simple metrics like Euclidean distance. In this line, a successful
strategy involves using multi-vector representations for documents and queries, where a
dimensional vector is produced for each token in the text. In this context, the similarity between
the query and the passage is measured using the so-called late interaction mechanism. This
mechanism works by computing the sum of the maximum similarities between each term of the
query and each term of a candidate passage. Although multi-vector representations enhance
efectiveness, they come at the cost of increased computational burden, including a larger
memory footprint and longer retrieval time.
1This paper is an extended abstract of Nardini et al. [
SEBD 2024: 32nd Symposium on Advanced Database Systems, June 23-26, 2024, Villasimius, Sardinia, Italy * Corresponding author.
© 2024 Copyright for this paper by its authors. Use permitted under Creative Commons License Attribution 4.0 International (CC BY 4.0).
Various approaches have been proposed to enhance the eficiency and reduce memory
demands in multi-vector systems. ColBERT [
This paper introduces EMVB, a novel framework designed for eficient query processing in
multi-vector dense retrieval. The key focus is on addressing the most time-consuming steps
identified in PLAID, which include: i) extracting the top-nprobe closest centroids during
candidate passage selection, ii) computing the centroid interaction mechanism, and iii) decompressing
quantized residuals. To address the first two steps, we propose a highly eficient passage filtering
approach based on optimized bit vectors. This approach significantly reduces the cost of
topnprobe extraction by identifying a small set of crucial centroid scores. Additionally, it decreases
the number of passages for which centroid interaction computation is necessary. We further
enhance eficiency in the second step by introducing a highly eficient column-wise reduction
leveraging SIMD instructions. For the third step, late interaction eficiency is improved by
introducing Product Quantization (PQ) [
Experimental evaluations on MS MARCO [
In a multi-vector dense retrieval scenario, an LLM encodes a passage into a collection of
dense -dimensional vector where is the number of tokens in the passage. Encoding each
token in each passage generates large collection, e.g., almost 600M of vectors for the 8.8M of
passages in MSMARCO. In virtue of this, ColBERTv2 [
¯, = ∑︁ max · ¯ =1 =1... , = ∑︁ max · .
=1 =1...
In the decompression phase the full-precision representation of is reconstructed by
combining the centroids and the residuals. Only the top-ndocs passages from the previous centroid
interaction step move to this step. Finally, PLAID applied late interaction [
PLAID execution time. We present a detailed analysis of PLAID’s execution time, delineating it into distinct phases such as retrieval, filtering , decompression, and late interaction. The experimentation adheres to the settings outlined in Section 4. The resulting execution times are reported for various values of , representing the number of retrieved passages.
Fast Closest Centroids Selection. The retrieval phase in PLAID is time consuming, as shown in Figure 1. This step concists of i) matrix multiplication between the query matrix and centroids for distance computation, ii) identify top-nprobe closest centroids, for each query term. Maybe surprisingly, the former step is the most time consuming (3× slower than matrix multiplication), even when performed with asymptotically linear algorithms such as quickselect. Our pre-filtering strategy, as explained in the subsequent paragraph, efectively accelerate the selection of the top-nprobe by minimizing the number of evaluated elements. In practice, we eficiently discard centroids with scores below a predefined threshold, and then exclusively apply quickselect to the remaining ones. As a result, in EMVB, the cost associated with extracting the top-nprobe becomes negligible, showcasing a speed improvement of two orders of magnitude when compared to extracting the top-nprobe from the complete set of centroids. ˜ Pre-filtering using bitvectors . Let us recall the definition of , , which represents the approximate score of the -th token of passage with respect to the -th term of the query , ˜ as defined in Equation 1. Estimating whether , has a large value is a proxy for estimating the importance of a passage w.r.t to the query. Given a passage , our pre-filtering consists in determining whether ˜ , , for = 1, . . . , , = 1, . . . , is large or not. Recall that ˜ , represents the approximate score of the -th token of passage with respect to the -th term of the query , as defined in Equation 1. Our pre-filtering approach works by checking if the centroid associated with (¯ ) belongs to the set of the closest centroids of . We define closeℎ as the set of centroids whose scores surpass a specified threshold ℎ in relation to a query term . For a certain passage , we also introduce the list of centroids ids , where is the centroid id of ¯ . The similarity of a passage with respect to a query can be rapidly estimated with our novel filtering function (, ) ∈ [0, ] with the following equation: (, ) = ∑︁ 1(∃ s.t. ∈ closeℎ).
=1 For a passage , this counts how many query terms have at least one similar passage term in , where “similar” describes the belonging of to closeℎ.
In Figure 2 (left), we present a performance comparison of our innovative pre-filter operating in conjunction with the centroid interaction mechanism (depicted by orange, blue, and green lines) against the performance of the centroid interaction mechanism applied to the entire set of candidate documents (indicated by the red dashed line) on the MS MARCO dataset. The plot illustrates that our pre-filtering approach eficiently eliminates non-relevant passages without adversely afecting the recall of the subsequent centroid interaction phase. For instance, we can significantly reduce the candidate passage set to just 1000 elements using a threshold of 0.4 without any compromise in R@100. In the subsequent sections, we detail the implementation of this pre-filter for optimal eficiency.
Building the bit vectors. Let = · , with ∈ [
The efectiveness of algorithms employing if-based structures is largely contingent on the
branch misprediction ratio. Contemporary CPUs speculate about the if condition’s outcome
by identifying patterns in the algorithm’s execution flow. If an incorrect branch prediction
occurs, a control hazard arises, leading to a pipeline flush with a delay of 15 to 20 clock
cycles, approximately 10. To address the ineficiency associated with branch misprediction,
we introduce a branchless algorithm. For a detailed description of the algorithm and of its
vectorized version, refer to the original paper [
Figure 2 (right) presents a comparison of our diferent approaches, namely "Naive IF," the "Vectorized IF," the "Branchless," and the "VecBranchless" described above. Branchless algorithms present a constant execution time, regardless of the value of the threshold, while if-based approaches ofer better performances as the value of ℎ increases. With ℎ ≥ 0.3, "Vectorized IF" is the most eficient approach, with a speedup up to 3 times compared to its naive counterpart. Fast set membership. We now move to the problem of computing Equation 4, assuming closeℎ to be known. Observe that this is a integer set membership problem, where we have to test if at least one member of belongs to closeℎ, with = 1, . . . , . Bit vectors (or bit array) are a widely adopted solution for implementing sets of integer values. A bit vector maps a set of integers up to into an array of bits, where the -th bit is set to one if and only if the integer is part of the set. Operations like addition and searching for any integer can be executed in constant time using bit manipulation operators. In terms of memory occupancy, a bit vectors requires /8 bytes. In our scenario, given that || = 218, a bit vector only needs 32 bytes for storage.
We further improve the eficiency of bit vectors by relying on the specific properties of our setting. As we need to search through all the bit vectors at a time, we rearrange the representation of the bit vectors by stacking them vertically (Figure 3). This allows to search a centroid index through all the closeℎ at a time. The bits corresponding to the same centroid for diferent query terms are consecutive and fit a 32-bit word. This way, we can simultaneously test the membership for all the queries in constant time with a single bitwise operation. In i <latexish1_b64="Sm7+HqTyJXkz 10 e ry ep (m iTm euq r )s 20 ep (m 10 iTm euq e ry detail, our algorithm starts by initializing a mask of = 32 bits at zeros (Step 1, Figure 3). Subsequently, for each term in the candidate documents, it performs a bitwise xor between the mask and the 32-bit word representing membership to all the query terms (Step 2, Figure 3). Consequently, Equation 4 can be derived by counting the number of 1s in at the end of the execution using the popcnt operation available in modern CPUs (Step 3, Figure 3). faster than the “Baseline” usage of bit vectors, and up to 30× faster than the centroid-interaction the closest centroid ¯ . Equation 3 becomes
Our pre-filtering approach allows us to eficiently filter out non-relevant passages and is
employed upstream of PLAID’s centroid interaction (Equation 2). The eficiency of the centroid
interaction itself can be improved by using our column-wise reduction approach. For reason
of space, we do not report the description of the algorithm in this discussion paper, and
we encourage the reader to refer to the original work [
max =1 =1... ∑︁
max =1 =1... ( · ¯ + · ) ≃ ( · ¯ + · ), (5) where and = − ¯ . Our experimental evaluation shows that PQ is both faster (up to 3.6× ) and more efective compared to the -bit compressor used in previous work. We propose to further improve the eficiency of the scoring phase by hinging on the properties of Equation 5. In many cases, we have that · ¯ > · ; hence the max operator on is lead by the score between the query term and the centroid, rather than the score between the query term and the residual. We argue that it is possible to compute the scores on the residuals only for a reduced set of document terms ¯ , where identifies the index of the query term. In particular, = {| · ¯ > ℎ}, where ℎ is a second threshold that determines whether the score with ¯ the centroid is suficiently large. With the introduction of this new per-term filter, Equation 5 now becomes computing the max operator on the set of passages in ¯ , i.e., , = ∑︁ max( · ¯ + · ).
¯ =1 ∈ (6) In practice, we compute the residual scores only for those document terms whose centroid score is large enough. If ¯ = ∅, we compute , as in Equation 5. We experimentally verify that this allows to save up to 30% in the late interaction with no performance degradation.
Experimental Settings. In this section, we compare our methodology with the state-of-the-art
engine for multi-vector dense retrieval, namely PLAID [
Table 2 presents a comparison between EMVB and PLAID in the out-of-domain evaluation on
the LoTTE dataset. Similar to PLAID [
10 100 1000
36 36 evaluation. This larger speedup, compared to MS MARCO, is attributed to the larger average document lengths in LoTTE. In this context, filtering non-relevant documents using our bit vector-based approach significantly impacts eficiency. It’s noteworthy that for the out-ofdomain evaluation, our pre-filtering method could be integrated into PLAID. This integration could maintain PLAID’s accuracy while benefiting from EMVB’s eficiency. Combinations of PLAID and EMVB are left for future exploration.
This work was supported by the EU - NGEU, by the PNRR - M4C2 - Investimento 1.3, Partenariato Esteso PE00000013 - “FAIR - Future Artificial Intelligence Research” - Spoke 1 “Human-centered AI” funded by the European Commission under the NextGeneration EU program, by the PNRR ECS00000017 Tuscany Health Ecosystem Spoke 6 “Precision medicine & personalized healthcare”, by the European Commission under the NextGeneration EU programme, by the Horizon Europe RIA “Extreme Food Risk Analytics” (EFRA), grant agreement n. 101093026, by the “Algorithms, Data Structures and Combinatorics for Machine Learning” (MIUR-PRIN 2017), and by the “Algorithmic Problems and Machine Learning” (MIUR-PRIN 2022).