2001 2002 0

1 Introduction↩︎

Multi-vector dense retrieval models, such as ColBERT [1] and XTR [2] are effective because of their expressiveness in modeling. While similar to single-vector dense models that represent information with a single contextualized embedding, such as DPR [3] and Qwen3-Embedding [4], multi-vector models use multiple vectors for each document to capture more granular information [5]. However, the number of vectors produced depends on the length of the documents; this creates efficiency challenges because this number is typically several orders of magnitude greater than for single vector representations. Subsequent work (PLAID [6]) addresses this problem by storing the vectors in an inverted file index (IVF) and by using product quantization via heavily compressed residuals [6]–[8]. Abstractly, at search time, PLAID first gathers document vectors that are similar to the query token vectors from the IVF, filters them using heuristics, and finally decompresses all document token vectors of the candidate documents to perform the actual scoring. Prior work has explored techniques such as token routing [9], score imputation [2], [10], fast decompression [10], instruction set optimization [11], and replacing the initial candidate search with more efficient models [12], [13] or even replacing the entire backbone with a smaller model [14] to reduce query latency. However, these lines of work do not address the index size problem. For one million documents, each with 512 tokens (a moderate size for a collection taking 1 to 3 GB to store without compression), PLAID still takes more than 7.8 GB to store aggressive 1-bit compressed residuals for the default ColBERT embedding size of 128. This size doubles or quadruples if using 2 or 4-bit compression [6], becoming an order of magnitude larger than the raw text.

Sparse retrieval, on the other hand, has a much smaller storage footprint. Since each document is represented by its unique tokens and impact scores [15], the index size is much smaller than in ColBERT, where each token maps to a dense vector (see Table 3 for comparison). Recent work in learned sparse retrieval (LSR) such as SPLADE [16]–[18] and MILCO [19] has improved model effectiveness substantially by mapping each document to a set of inferred tokens; this still keeps the index size manageable [20], [21].

Interestingly, without the residual, PLAID is essentially a sparse retrieval with a binary document weight (more in the next section). However, residuals, while composing most of the index storage, are critical for calculating the approximated ColBERT score in PLAID (see Table 2 for empirical results). To remove the dependency on residual vectors we introduce ColBERTSaR, a sparse approximation of the MaxSim score of any ColBERT-style model without retraining the retrieval model and storing the residuals. ColBERTSaR is a drop-in replacement for PLAID that transforms ColBERT into a sparse retrieval model. ColBERTSaR substantially reduces PLAID’s index size while providing competitive effectiveness. In this work, we 1) provide a theoretical derivation of the ColBERTSaR sparse approximation; 2) establish strong connections between ColBERT and LSR models; and 3) present empirical results on monolingual, cross-language, and multilingual retrieval using a proof-of-concept implementation.¹

2 ColBERTSaR↩︎

2.1 Sparse Approximation of MaxSim↩︎

MaxSim, proposed by [1], aggregates the pairwise similarities between query and document token embeddings, which are implemented as the dot products of L2-normalized embeddings. Let \(q_i\in q\) and \(d_j\in d\) be the token embeddings of query \(q\) and document \(d\). MaxSim can be written as \[Score(q, d) = \sum_{i=1}^{|q|} \max_{j=1}^{|d|} \left(q_i \cdot d_j\right)\] where \(|q|\) and \(|d|\) denote the length of the query and document.

While expressive and effective, this process is expensive in two ways. First, while all inner product pairs are needed to find the maximum, only a few contribute to the final score (specifically \(|q|/|d|\), which is 6.25% when query and document lengths are 32 and 512, a common setting). Second, storing \(|d|\) embeddings is expensive. ColBERT [1] stored all embeddings with 16-bit floats for each of the 128 dimensions. PLAID [6] further compressed the embeddings as a cluster centroid and a residual with several bits per coordinate. The MaxSim scoring function can be rewritten as: \[Score(q, d) = \sum_{i=1}^{|q|} \max_{j=1}^{|d|} \left( q_i \cdot \left(c_{d_j} + r_j\right) \right)\] where \(c_{d_j}\) is the closest anchor to \(d_j\) and \(r_j=d_j-c_{d_j}\) is the residual embedding (which can be assigned at indexing time).² Anchor matrix \(C\), with \(K\) centroids, each as a column vector, \(c_k\), is fitted using K-means clustering on a sample of the document token embeddings. MaxSim calculation can be further optimized by only taking the maximum of document embeddings that are in the \(n\) closest partitions of \(q_i\) instead of over all anchors \(c_k\), which is the nprobe parameter in ANN algorithms [22].

If the residual norms are small (generally the assumption when using small nprobe), residual vectors can be omitted. This approximation makes the function depend only on the query/centroid inner products, which are free since we already calculated them to determine the closest clusters to \(q_i\) when using \(nprobe\). The scoring function can then be further simplified as: \[\begin{align} Score^S(q, d) &= \sum_{i=1}^{|q|} \max_{j=1}^{|d|} \left( q_i \cdot c_{d_j} \right) = \sum_{i=1} \max_{k\in v_d} q_i \cdot c_k \nonumber \\ &= \sum_{i=1}^{|q|} \max_{k=1}^{K} q_i \cdot c_k \cdot \mathbb{1}(k\in v_d) \label{eq:centroid-approx} \end{align}\tag{1}\] where \(v_d = \{ c_{d_j}| \forall d_j \in d\}\) is the set of anchors that all tokens in document \(d\) are closest to and \(\mathbb{1}(\cdot)\) is the indicator function. This is also the first stage candidate gathering process in PLAID.

The core of Equation 1 is a dynamic TF-IDF function. Interpreting the anchors \(c_k\) as a sparse index vocabulary, the inner product between each \(q_i\) and \(c_k\) can be seen as a query token weighting, or a query-specific inverse document frequency. This allows us to use the inverted index infrastructure for sparse retrieval. Using this residual-free product quantization, ColBERT is a learned sparse retrieval model with complex score aggregation.

2.2 Query-Aware and Unsupervised Anchor Optimization↩︎

Fitting the anchors using K-means clustering minimizes the distance from each training sample embedding to the centroids; this can be written as a minimization problem [23]. Assuming \(M\) training examples and \(K\) centroids, the target can be written: \[\min_{C} \sum_{j=1}^M \min_{k=1}^K \left(c_k - x_j\right)^2 \label{eq:kmeans}\tag{2}\] where \(x_j\) are the training embeddings. In other words, K-means minimizes the L2 norm of residual vectors \(r\), which is the difference between its closest centroid and itself. Optimization usually uses an iterative algorithm such as E-M but can also be done with gradient descent [23]; this gives us more flexibility for extensions.

However, the approximation error between true MaxSim and the residual-free quantization depends not only on the size but also on the direction of the residual vectors, which differs from the K-means clustering optimization goal. If all residual vectors are zero there is no approximation error. Otherwise, let \(m(i) = \mathop{\mathrm{arg\,max}}_j q_i \cdot d_j\), the approximation error can be written as: \[\begin{align} Score(q, d) - Score^S(q, d) &= \sum_i q_i \cdot \left( d_{m(i)} - c_{m(i)} \right) = \sum_i q_i \cdot r_{m(i)} \end{align}\] which is the sum of the dot product between each query token embedding and the residual vector of its matching document token. Although minimizing the norm of the residual vectors \(r\) can indirectly reduce approximation error, we can directly optimize for the approximation error by modifying Equation 2 to be query-aware: \[\min_{C} \sum_{i=1}^N \sum_{j=1}^M q_i \cdot \mathop{\mathrm{arg\,min}}_{c_k, \forall k\in[K]} \left(c_k - x_j\right)^2 \label{eq:query-aware-anchors}\tag{3}\] where \(N\) is the number of training queries. We call this query-aware anchor optimization.

However, Equation 3 requires training queries, which are usually not present during indexing. Although they can be mined from existing or publicly available query logs (feasible in production settings), the assumed query distribution may be different from actual queries. We can, instead, use in-batch training examples as pseudo-queries to remove the dependency on training queries. Let \(B\) be training mini-batch size. Mini-batch minimization can be written as: \[\min_{C} \sum_{i=1}^B \sum_{j=1}^B x_i \cdot \mathop{\mathrm{arg\,min}}_{c_k, \forall k\in[K]} \left(c_k - x_j\right)^2 \label{eq:unsupervised-anchors}\tag{4}\] which forms the unsupervised anchor optimization problem.

Equation 4 assumes that query embeddings and document token embeddings are similar, which sometimes is false. However, it augments training optimization using only document token vectors without additional resources. To simulate scenarios where query logs or external queries exist, we explore using Equation 3 with training queries from evaluation collections and from MS MARCO (see Section 4.1).

2.3 Sparse Indexing and Retrieval↩︎

Indexing begins by sampling document token embeddings to form a training set for the anchor matrix \(C\). The number of anchors \(K\) is a hyperparameter dependent on the number of documents being indexed. Anchors created during training are used to sparsify the document token embeddings. Each document token is assigned to its closest anchor based on the token embedding, forming a set of documents associated with each anchor point. At search time, the \(n\) closest anchors to each query token embedding are identified. All documents in at least one anchor set are considered candidate documents. We then use a forward index that maps each document to its corresponding anchors to produce \(Score^S(q, d)\) (Equation 1 ).

2.3.1 Sparse Indexing↩︎

To reduce disk I/O, the collection is processed in mini-batches and stored in multiple chunks. After producing ColBERT token embeddings \(d_j\) for each document \(d\), we calculate the dot product of \(d_j\) with the trained anchor matrix \(c\). The coordinate ID of the highest scoring anchor is used as the mapped anchor for each document token \(d_j\). Each chunk is an inverted mapping from an anchor ID to the set of doc IDs containing it.

After all chunks are stored, we merge them using \(n\)-way merge to produce the final inverted index. For simplicity, we use SciPy CSR Matrix to store the inverted index and produce the forward index by inverting the inverted matrix. While engineering optimizations such as blocking and sketch vectors can further improve efficiency, this simple process is a proof-of-concept for storing sparse document representations to support ColBERT scoring approximation.

2.3.2 Searching↩︎

Each query is first encoded using ColBERT to get query token embeddings \(q_i\). The dot product with the anchor matrix \(C\) produces full query token-to-anchor scores \(S\in \mathbb{R}^{N\times K}\).

First stage scoring selects the top \(n\) anchors (i.e., nprobe) for each query token \(q_i\). For each \(q_i\), we collect all document IDs from the postings list across the \(n\) anchors to approximate Equation 1 with only the top-\(n\) anchors, identical to PLAID [6]. This can be done efficiently with only a single pass over the inverted index.

Second stage scoring uses the forward index to map the top \(k\) first-stage documents to the anchor IDs they contain. It then slices the query token-anchor score matrix \(S\) using these IDs and uses Equation 1 to produce \(Score^S\).

Since the inverted index traversal is not a standard SciPy operation, we implemented the single-pass traversal algorithm in Cython, which produced executable Python functions. Optimization of the max operator in an inverted index requires more investigation, which we leave to future work. Therefore, in this work, we omit the latency analysis and focus on the trade-off between index size and retrieval effectiveness.

3 Experiments↩︎

We evaluate ColBERTSaR on BEIR [24], NeuCLIRBench [25] (English queries with Chinese, Persian and Russian documents), and NeuCLIRTech [26] (English queries and Chinese academic abstracts), which cover monolingual, cross-language (CLIR), and multilingual (MLIR) ad hoc retrieval. In the CLIR setting of NeuCLIRBench, we use English queries and retrieve documents from each of the three language-specific collections (Chinese, Persian and Russian). In the MLIR setting, queries are still in English, but the document collection is a mixture of the three.

To demonstrate the space reduction and effectiveness, we compare ColBERTSaR to PLAID using three backbone ColBERT models: ColBERT-Small-v1 [27]³ and English-Trained PLAID-X [28]⁴ for monolingual English retrieval on BEIR, and MTD PLAID-X [29]⁵ for CLIR and MLIR on NeuCLIRBench and NeuCLIRTech. All documents are split into passages of 512 tokens and aggregate passage scores with MaxP.

As baselines, we compare with BM25 (machine-translated documents, i.e., DT, on NeuCLIRBench and NeuCLIRTech provided by the benchmark to perform lexical matching on English tokens) as the lexical sparse retrieval alternative. We also compare with SPLADEv3 [18] for BEIR, and MILCO [19], a state-of-the-art multilingual LSR model, for CLIR and MLIR as the LSR alternatives.

For fitting ColBERTSaR anchors, we fix the number of anchors at 500k for NeuCLIRTech and small BEIR datasets (datasets with fewer than 1M passages; results summarized at the left of Table 2), and one million for others. The number of sampled training passages follows the sampling rate in PLAID for fitting the K-means clusters, which is \(16\times\sqrt{\bar{|d|}\times D}\) where \(\bar{|d|}\) is the assumed document length (120 by default) and \(D\) is the number of documents in the collection. We use eight NVIDIA V100 GPUs and a learning rate of \(10^{-4}\) with a per-device batch size of 2048 vectors for 100k training steps using fp16.

4 Results↩︎

Our experiments show that our ColBERTSaR engine provides competitive effectiveness compared to the PLAID engine with one bit residual compression while substantially reducing the index size. Summarized in Table 1, ColBERTSaR is capable of representing document token vectors effectively without being aware that query vectors will be in a very different distribution (i.e., in a different language). ColBERTSaR demonstrates competitive effectiveness to MILCO, the state-of-the-art multilingual LSR model, indicating that our proposed method is an effective way to sparsify a multi-vector dense retrieval model. The gap between PLAID and ColBERTSaR on the NeuCLIRTech CLIR task is slightly bigger than on NeuCLIRBench variants, indicating that technical terminology in the documents creates challenges for ColBERTSaR when representing the document tokens.

ColBERTSaR reduces the index size from 77% (zho) to 53% (MLIR),⁶ as the index size of each subset in the NeuCLIRBench collection is summarized in Table 3. While ColBERTSaR indices are still larger than MILCO’s, which are Lucene indices, engineering tricks such as bit packing can minimize the ColBERTSaR indices.

Table 2 summarizes the nDCG@10 scores on the 13 BEIR subsets with two ColBERT base models. ColBERTSaR maintains 92% (0.481 to 0.445) and 89% (0.548 to 0.490) effectiveness compared to PLAID with one bit residual compression, with PLAID XLMR ET and colbert-small-v1, respectively. The larger effectiveness gaps appear mostly in question-answering subsets such as Quora, Fever, Hotpot QA, MSMARCO, and Natural Questions. These subsets generally contain entities with specific meanings that are challenging for contextualized token embeddings to capture; this is a known weakness for ColBERT-style models [30]. ColBERTSaR amplifies such weakness since each document token embedding is further mapped to a centroid that may be mixed with other meanings for each token. By fusing with BM25 (last row in Table 2) using reciprocal rank fusion [31] we are able to recover some effectiveness on these QA-style queries while hurting other subsets, resulting in a slight increase in the average nDCG@10. However, with some reasonable prior knowledge in query distribution it is feasible to pick a suitable stack for the task without much overhead in index size or retrieval, since the BM25 index is relatively cheap to store and search (see Table 3). Furthermore, compared to PLAID with no residuals (0 bit), essentially ColBERTSaR by using K-means centroids as anchors, ColBERTSaR optimization substantially improves the anchor when representing document tokens with no residuals.

4.1 Query Source for Anchor Optimization↩︎

While ColBERTSaR uses in-batch documents as pseudo queries when fitting the anchors, we can use other queries during this process by assuming certain query characteristics. At the bottom of Table 2, we observe that using the official BEIR training queries or the MS MARCO training queries may lead to a slight improvement. However, training queries are not always available, and assuming that queries are similar to MS MARCO-style may also be less optimal (although many ColBERT models were trained on MS MARCO queries [1], [28], [29], so it may be a fair assumption to reintroduce them at the indexing phase). Here, using in-batch document tokens as the query is still likely to be the most robust solution, as it only requires a sample of documents; these will always be available at the indexing phase.

4.2 Searching with Different nprobe↩︎

One of the critical hyperparameters at query time is nprobe, which is a key parameter in ANN search [22] to control the search space at search time. Naturally, the higher nprobe, i.e., the more anchors we explore, the more accurate the first stage of ColBERTSaR retrieval is. In Figure 1, we observe a diminishing return when increasing nprobe. Particularly when there is a second stage that uses a forward index to calculate the actual scores the final effectiveness saturates at around two to four probes. When using only the inverted index, effectiveness saturates on smaller collections (zho and fas in NeuCLIRBench) but continues to improve on larger ones. This shows that the amount of exploration depends on the size of the collection, which is expected since there are more points in the index to gather scores.

5 Conclusion and Future Work↩︎

This work introduces ColBERTSaR, a sparse approximation of ColBERT, that substantially reduces index size with competitive effectiveness. This novel approach provides critical insight into connecting multi-vector dense retrieval and LSR. Further engineering, such as document term weightings and index traversal tricks, will be critical to move beyond this proof-of-concept implementation.

References↩︎