Towards Lossless Token Pruning in Late-Interaction Retrieval Models
Yuxuan Zong, Benjamin Piwowarski · 2025
Read Towards Lossless Token Pruning in Late-Interaction Retrieval Models by Yuxuan Zong, Benjamin Piwowarski (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2504-12778.txt.
Introduction
Yuxuan Zong and Benjamin Piwowarski shrink the storage of top search models in 2025 without dulling their aim. Late-interaction models score a query against every word-piece of every document, which ranks well but eats memory for all those stored pieces. Past pruning cut pieces by rules of thumb, with no promise the score would survive.
Their fix starts from a clean rule for when a piece can go with zero score change. Three added training goals push the model toward shapes where most pieces are safe to cut, and two cutting plans apply the rule. In tests at home and abroad, the model kept its ranking quality while storing only thirty percent of its pieces, they report. Memory savings that size decide whether such search runs on one machine or a rack.
Catalog record
| CREATOR | Yuxuan Zong, Benjamin Piwowarski |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 56 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2504-12778
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Towards Lossless Token Pruning in Late-Interaction Retrieval Models Yuxuan Zong, Benjamin Piwowarski Abstract . Late interaction neural IR models like ColBERT offer a competitive effectiveness-efficiency trade-off across many benchmarks. However, they require a huge memory space to store the contextual representation for all the document tokens. Some works have proposed using either heuristics or statistical-based techniques to prune tokens from each document. This however doesn’t guarantee that the removed tokens have no impact on the retrieval score. Our work uses a principled approach to define how to prune tokens without impacting the score between a document and a query. We introduce three regularization losses, that induce a solution with high pruning ratios, as well as two pruning strategies. We study them experimentally (in and out-domain), showing that we can preserve ColBERT’s performance while using only 30% of the tokens. Conference: Proceedings of the 48th International ACM SIGIR Conference on Research and Development in Information Retrieval; July 13–18, 2025; Padua, Italy Proceedings of the 48th International ACM SIGIR Conference on Research and Development in Information Retrieval (SIGIR ’25), July 13–18, 2025, Padua, Italy DOI: 10.1145/3726302.3730100 ISBN: 979-8-4007-1592-1/2025/07 CCS: Information systems Document representation CCS: Information systems Retrieval models and ranking CCS: Information systems Information retrieval † † cc-license: by-nd 1. Introduction Pre-trained contextualized language models based on the Transformer architecture, such as BERT, significantly improved retrieval effectiveness over the previous state-of-the-art methods in information retrieval (IR) like e.g. BM25 ( Robertson et al., 1994 ) . Among these models, dual encoders such as sparse ( Formal et al., 2021 ; Gao et al., 2021 ) or dense ( Karpukhin et al., 2020 ) models, have the best efficiency while cross-encoders, e.g. MonoBERT ( Nogueira and Cho, 2020 ) , have the best effectiveness. Another category of models, called late interaction models, like ColBERT ( Khattab and Zaharia, 2020 ; Santhanam et al., 2022b ) , offer a good efficiency-effectiveness trade-off, as they are halfway between dual encoders and cross-encoders. Specifically, unlike dual encoders, late interaction models use embeddings at the token level rather than to represent the entire query or document. In ColBERT, the score of a document for one query token is defined as the maximum of the inner product over all the document tokens representations with the query token representation. This token-level granularity allows for finer semantic matching and improved retrieval accuracy. Moreover, compared to the cross-encoder mechanism like MonoBERT ( Nogueira and Cho, 2020 ) , this "late interaction" mechanism provides a way to build an index of a whole dataset by storing the document token representations, or document vectors in short. Figure 1. Illustration of the concept of dominance. In this example, \mathbf{d}_{3} is dominated by \mathbf{d}_{1} and \mathbf{d}_{2} . \mathbf{d}_{3} can be removed from the document representation without changing a modified ColBERT scoring function (see Section 3.2 ). Despite its low norm, \mathbf{d}_{2} is kept since it brings new information about the relevance of the document. The hashed area corresponds to the half-space where the inner product of any vector with \mathbf{d}_{3} is negative. The gray area is discussed in Section 3.1 . However, storing the vectors of the documents requires a large index space compared to dual encoding approaches. For example, for MS MARCO v1 ( Bajaj et al., 2018 ) , composed of 8.8M passages, the ColBERT index takes 142 GiB. PLAID ( Santhanam et al., 2022a ) , which is a highly optimized version of ColBERTv2, requires more than 20 GiB of space. This is in contrast to the 13 GiB needed to store the 768-dimensional vectors of a dense model (without any compression, using FP16). Furthermore, a large index leads to expensive computational costs; as in ColBERT’s retrieval pipeline, the retrieval cost scales linearly with the query and document’s length. To reduce the index size, some works have proposed to prune tokens from the document. Some existing works ( Lassance et al., 2022 ; Acquavia et al., 2023 ; Liu et al., 2024 ) propose to use static methods based on heuristic or statistical approaches, but they degrade ColBERT performance with high pruning ratios, greater than 50%. Some other works ( Qian et al., 2022 ; Hofstätter et al., 2022 ) learn to discard some tokens using a gating mechanism, and hence aim at learning sparse (at token level) document representation. These methods remove some of the unimportant tokens, but do not consider how to remove tokens while having a minimum impact on the ColBERT score. This can be a problem, as illustrated in Figure 1 , where the document vector \mathbf{d}_{2} , while having the lowest norm, can still match a query token – i.e., the inner product with a query vector located in the green area will be maximized by \mathbf{d}_{2} . In the same document, \mathbf{d}_{3} could, however, be pruned without changing the score of the document, since either \mathbf{d}_{1} , \mathbf{d}_{2} or \mathbf{d}_{4} would match any query token located in the blue, red or green areas. In this paper, we first formally define this lossless pruning strategy and show that it is equivalent to a linear programming problem. We then propose different training methodologies and approximate pruning strategies that can be used in practice. Finally, through our experiments, we analyze the performance of our proposed approach considering different pruning strategies and regularizations, leading to the removal of 70% tokens and a performance drop of less than 1.5% on in-domain datasets. For the out-of-domain evaluation task, we also end up with a 65% token removal with less than a 3% drop in the performance on BEIR task (1.1% of performance drop in the LoTTE search). We release the experimental code connected to this paper 1 1 1 https://github.com/yzong12138/MVDR_pruning . In the following, we report the research questions that are tackled in this paper, as well as our different contributions. RQ1 Is it possible to define a late interaction model and a pruning algorithm that guarantees that the score of a document does not change whatever the query? In Section 3 , we formally define the concept of “dominance” whereby a document vector can be removed from a document’s representation without impacting a late interaction scoring function. More precisely, in Section 3.1 we discuss how to modify the ColBERT scoring function to allow for more pruning without impacting its performance, and in Section 3.2 , we show how the problem of pruning document tokens with the guarantee of not modifying the score of the document , that is, lossless pruning , is equivalent to a Linear Programming problem ( Nocedal and Wright, 2006 ) . RQ2 How can this motivate regularization (during training) and practical pruning strategies (before inference), and what is the effectiveness/efficiency trade-off of our overall methodology for late-interaction models? In Section 4 , we propose three regularizations (so that more document tokens are dominated) as well as two pruning strategies that help to increasing the pruning ratio. In Sections 6.1 and 6.2 , we conduct extensive experiments based on these strategies that show that we can achieve a competitive efficiency-effectiveness trade-off. RQ3 How is our proposed regularization and the pruning strategy perform on out-of-domain datasets? As regularization might prevent the model from generalizing to out-of-domain datasets, we conduct