{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,16]],"date-time":"2026-07-16T05:15:57Z","timestamp":1784178957266,"version":"3.55.0"},"reference-count":50,"publisher":"Association for Computing Machinery (ACM)","issue":"5","license":[{"start":{"date-parts":[[2024,4,29]],"date-time":"2024-04-29T00:00:00Z","timestamp":1714348800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Inf. Syst."],"published-print":{"date-parts":[[2024,9,30]]},"abstract":"<jats:p>With the development of pre-trained language models, the dense retrieval models have become promising alternatives to the traditional retrieval models that rely on exact match and sparse bag-of-words representations. Different from most dense retrieval models using a bi-encoder to encode each query or document into a dense vector, the recently proposed late-interaction multi-vector models (i.e., ColBERT and COIL) achieve state-of-the-art retrieval effectiveness by using all token embeddings to represent documents and queries and modeling their relevance with a sum-of-max operation. However, these fine-grained representations may cause unacceptable storage overhead for practical search systems. In this study, we systematically analyze the matching mechanism of these late-interaction models and show that the sum-of-max operation heavily relies on the co-occurrence signals and some important words in the document. Based on these findings, we then propose several simple document pruning methods to reduce the storage overhead and compare the effectiveness of different pruning methods on different late-interaction models. We also leverage query pruning methods to further reduce the retrieval latency. We conduct extensive experiments on both in-domain and out-domain datasets and show that some of the used pruning methods can significantly improve the efficiency of these late-interaction models without substantially hurting their retrieval effectiveness.<\/jats:p>","DOI":"10.1145\/3639818","type":"journal-article","created":{"date-parts":[[2024,1,31]],"date-time":"2024-01-31T12:00:27Z","timestamp":1706702427000},"page":"1-28","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":6,"title":["An Analysis on Matching Mechanisms and Token Pruning for Late-interaction Models"],"prefix":"10.1145","volume":"42","author":[{"ORCID":"https:\/\/orcid.org\/0009-0000-4144-938X","authenticated-orcid":false,"given":"Qi","family":"Liu","sequence":"first","affiliation":[{"name":"Being Key Laboratory of Data Management and Analysis Methods, Gaoling School of Artificial Intelligence, Renmin University of China, Beijing, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0009-0003-8516-3035","authenticated-orcid":false,"given":"Gang","family":"Guo","sequence":"additional","affiliation":[{"name":"Being Key Laboratory of Data Management and Analysis Methods, Gaoling School of Artificial Intelligence, Renmin University of China, Beijing China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-9257-5498","authenticated-orcid":false,"given":"Jiaxin","family":"Mao","sequence":"additional","affiliation":[{"name":"Being Key Laboratory of Data Management and Analysis Methods, Gaoling School of Artificial Intelligence, Renmin University of China, Beijing China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-9781-948X","authenticated-orcid":false,"given":"Zhicheng","family":"Dou","sequence":"additional","affiliation":[{"name":"Being Key Laboratory of Data Management and Analysis Methods, Gaoling School of Artificial Intelligence, Renmin University of China, Beijing China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-9777-9676","authenticated-orcid":false,"given":"Ji-Rong","family":"Wen","sequence":"additional","affiliation":[{"name":"Being Key Laboratory of Data Management and Analysis Methods, Gaoling School of Artificial Intelligence, Renmin University of China, Beijing China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2306-7596","authenticated-orcid":false,"given":"Hao","family":"Jiang","sequence":"additional","affiliation":[{"name":"Distributed and Parallel Software Lab, Huawei, Hangzhou China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-6829-4522","authenticated-orcid":false,"given":"Xinyu","family":"Zhang","sequence":"additional","affiliation":[{"name":"Distributed and Parallel Software Lab, Huawei, Hangzhou China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4214-7858","authenticated-orcid":false,"given":"Zhao","family":"Cao","sequence":"additional","affiliation":[{"name":"Distributed and Parallel Software Lab, Huawei, Hangzhou China"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2024,4,29]]},"reference":[{"key":"e_1_3_2_2_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-59212-7_13"},{"key":"e_1_3_2_3_2","doi-asserted-by":"publisher","DOI":"10.1145\/2094072.2094074"},{"key":"e_1_3_2_4_2","doi-asserted-by":"publisher","DOI":"10.1145\/1409220.1409223"},{"key":"e_1_3_2_5_2","article-title":"SparTerm: Learning term-based sparse representation for fast text retrieval","author":"Bai Yang","year":"2020","unstructured":"Yang Bai, Xiaoguang Li, Gang Wang, Chaoliang Zhang, Lifeng Shang, Jun Xu, Zhaowei Wang, Fangshan Wang, and Qun Liu. 2020. SparTerm: Learning term-based sparse representation for fast text retrieval. arXiv preprint arXiv:2010.00768 (2020).","journal-title":"arXiv preprint arXiv:2010.00768"},{"key":"e_1_3_2_6_2","unstructured":"Payal Bajaj Daniel Campos Nick Craswell Li Deng Jianfeng Gao Xiaodong Liu Rangan Majumder Andrew McNamara Bhaskar Mitra Tri Nguyen Mir Rosenberg Xia Song Alina Stoica Saurabh Tiwary and Tong Wang. 2018. MS MARCO: A human generated machine reading comprehension dataset. arXiv preprint arXiv:1611.09268 (2018)."},{"key":"e_1_3_2_7_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-71496-5_9"},{"key":"e_1_3_2_8_2","doi-asserted-by":"publisher","DOI":"10.1145\/1658377.1658378"},{"key":"e_1_3_2_9_2","doi-asserted-by":"publisher","DOI":"10.1145\/1183614.1183644"},{"key":"e_1_3_2_10_2","doi-asserted-by":"publisher","DOI":"10.1145\/383952.383958"},{"key":"e_1_3_2_11_2","article-title":"Context-aware sentence\/passage term importance estimation for first stage retrieval","author":"Dai Zhuyun","year":"2019","unstructured":"Zhuyun Dai and Jamie Callan. 2019. Context-aware sentence\/passage term importance estimation for first stage retrieval. arXiv preprint arXiv:1910.10687 (2019).","journal-title":"arXiv preprint arXiv:1910.10687"},{"key":"e_1_3_2_12_2","doi-asserted-by":"publisher","DOI":"10.1145\/3366423.3380258"},{"key":"e_1_3_2_13_2","article-title":"BERT: Pre-training of deep bidirectional transformers for language understanding","author":"Devlin Jacob","year":"2018","unstructured":"Jacob Devlin, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova. 2018. BERT: Pre-training of deep bidirectional transformers for language understanding. arXiv preprint arXiv:1810.04805 (2018).","journal-title":"arXiv preprint arXiv:1810.04805"},{"key":"e_1_3_2_14_2","article-title":"SPLADE v2: Sparse lexical and expansion model for information retrieval","author":"Formal Thibault","year":"2021","unstructured":"Thibault Formal, Carlos Lassance, Benjamin Piwowarski, and St\u00e9phane Clinchant. 2021. SPLADE v2: Sparse lexical and expansion model for information retrieval. arXiv preprint arXiv:2109.10086 (2021).","journal-title":"arXiv preprint arXiv:2109.10086"},{"key":"e_1_3_2_15_2","doi-asserted-by":"publisher","DOI":"10.1145\/3404835.3463098"},{"key":"e_1_3_2_16_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-72240-1_23"},{"key":"e_1_3_2_17_2","doi-asserted-by":"publisher","DOI":"10.1145\/32206.32212"},{"key":"e_1_3_2_18_2","doi-asserted-by":"publisher","DOI":"10.18653\/v1\/2021.naacl-main.241"},{"key":"e_1_3_2_19_2","doi-asserted-by":"publisher","DOI":"10.1145\/3511808.3557367"},{"key":"e_1_3_2_20_2","doi-asserted-by":"publisher","DOI":"10.1145\/3394486.3403305"},{"key":"e_1_3_2_21_2","volume-title":"International Conference on Learning Representations","author":"Humeau Samuel","year":"2019","unstructured":"Samuel Humeau, Kurt Shuster, Marie-Anne Lachaux, and Jason Weston. 2019. Poly-encoders: Architectures and pre-training strategies for fast and accurate multi-sentence scoring. In International Conference on Learning Representations."},{"key":"e_1_3_2_22_2","doi-asserted-by":"publisher","DOI":"10.1109\/TBDATA.2019.2921572"},{"key":"e_1_3_2_23_2","doi-asserted-by":"publisher","DOI":"10.18653\/v1\/2020.emnlp-main.550"},{"key":"e_1_3_2_24_2","doi-asserted-by":"publisher","DOI":"10.1145\/3397271.3401075"},{"key":"e_1_3_2_25_2","volume-title":"International Conference on Learning Representations","author":"Lan Zhenzhong","year":"2019","unstructured":"Zhenzhong Lan, Mingda Chen, Sebastian Goodman, Kevin Gimpel, Piyush Sharma, and Radu Soricut. 2019. ALBERT: A lite BERT for self-supervised learning of language representations. In International Conference on Learning Representations."},{"key":"e_1_3_2_26_2","article-title":"A static pruning study on sparse neural retrievers","author":"Lassance Carlos","year":"2023","unstructured":"Carlos Lassance, Simon Lupart, Herv\u00e9 Dejean, St\u00e9phane Clinchant, and Nicola Tonellotto. 2023. A static pruning study on sparse neural retrievers. arXiv preprint arXiv:2304.12702 (2023).","journal-title":"arXiv preprint arXiv:2304.12702"},{"key":"e_1_3_2_27_2","article-title":"A study on token pruning for ColBERT","author":"Lassance Carlos","year":"2021","unstructured":"Carlos Lassance, Maroua Maachou, Joohee Park, and St\u00e9phane Clinchant. 2021. A study on token pruning for ColBERT. arXiv preprint arXiv:2112.06540 (2021).","journal-title":"arXiv preprint arXiv:2112.06540"},{"key":"e_1_3_2_28_2","article-title":"A few brief notes on DeepImpact, COIL, and a conceptual framework for information retrieval techniques","author":"Lin Jimmy","year":"2021","unstructured":"Jimmy Lin and Xueguang Ma. 2021. A few brief notes on DeepImpact, COIL, and a conceptual framework for information retrieval techniques. arXiv preprint arXiv:2106.14807 (2021).","journal-title":"arXiv preprint arXiv:2106.14807"},{"key":"e_1_3_2_29_2","doi-asserted-by":"publisher","DOI":"10.1145\/3404835.3463238"},{"key":"e_1_3_2_30_2","article-title":"RoBERTa: A robustly optimized BERT pretraining approach","author":"Liu Yinhan","year":"2019","unstructured":"Yinhan Liu, Myle Ott, Naman Goyal, Jingfei Du, Mandar Joshi, Danqi Chen, Omer Levy, Mike Lewis, Luke Zettlemoyer, and Veselin Stoyanov. 2019. RoBERTa: A robustly optimized BERT pretraining approach. arXiv preprint arXiv:1907.11692 (2019).","journal-title":"arXiv preprint arXiv:1907.11692"},{"key":"e_1_3_2_31_2","doi-asserted-by":"publisher","DOI":"10.1162\/tacl_a_00369"},{"key":"e_1_3_2_32_2","doi-asserted-by":"publisher","DOI":"10.1145\/3404835.3463030"},{"key":"e_1_3_2_33_2","article-title":"Passage re-ranking with BERT","author":"Nogueira Rodrigo","year":"2019","unstructured":"Rodrigo Nogueira and Kyunghyun Cho. 2019. Passage re-ranking with BERT. arXiv preprint arXiv:1901.04085 (2019).","journal-title":"arXiv preprint arXiv:1901.04085"},{"key":"e_1_3_2_34_2","article-title":"From doc2query to docTTTTTquery","author":"Nogueira Rodrigo","year":"2019","unstructured":"Rodrigo Nogueira, Jimmy Lin, and AI Epistemic. 2019. From doc2query to docTTTTTquery. Online preprint (2019).","journal-title":"Online preprint"},{"key":"e_1_3_2_35_2","article-title":"Document expansion by query prediction","author":"Nogueira Rodrigo","year":"2019","unstructured":"Rodrigo Nogueira, Wei Yang, Jimmy Lin, and Kyunghyun Cho. 2019. Document expansion by query prediction. arXiv preprint arXiv:1904.08375 (2019).","journal-title":"arXiv preprint arXiv:1904.08375"},{"key":"e_1_3_2_36_2","doi-asserted-by":"publisher","DOI":"10.1145\/290941.291008"},{"key":"e_1_3_2_37_2","article-title":"Multi-vector retrieval as sparse alignment","author":"Qian Yujie","year":"2022","unstructured":"Yujie Qian, Jinhyuk Lee, Sai Meher Karthik Duddu, Zhuyun Dai, Siddhartha Brahma, Iftekhar Naim, Tao Lei, and Vincent Y. Zhao. 2022. Multi-vector retrieval as sparse alignment. arXiv preprint arXiv:2211.01267 (2022).","journal-title":"arXiv preprint arXiv:2211.01267"},{"key":"e_1_3_2_38_2","article-title":"Understanding the behaviors of BERT in ranking","author":"Qiao Yifan","year":"2019","unstructured":"Yifan Qiao, Chenyan Xiong, Zhenghao Liu, and Zhiyuan Liu. 2019. Understanding the behaviors of BERT in ranking. arXiv preprint arXiv:1904.07531 (2019).","journal-title":"arXiv preprint arXiv:1904.07531"},{"key":"e_1_3_2_39_2","unstructured":"Alec Radford Jeffrey Wu Rewon Child David Luan Dario Amodei and Ilya Sutskever. 2019. Language models are unsupervised multitask learners. OpenAI blog 1 8 (2019) 9."},{"key":"e_1_3_2_40_2","article-title":"Exploring the limits of transfer learning with a unified text-to-text transformer","author":"Raffel Colin","year":"2019","unstructured":"Colin Raffel, Noam Shazeer, Adam Roberts, Katherine Lee, Sharan Narang, Michael Matena, Yanqi Zhou, Wei Li, and Peter J. Liu. 2019. Exploring the limits of transfer learning with a unified text-to-text transformer. arXiv preprint arXiv:1910.10683 (2019).","journal-title":"arXiv preprint arXiv:1910.10683"},{"key":"e_1_3_2_41_2","doi-asserted-by":"publisher","DOI":"10.1561\/1500000019"},{"key":"e_1_3_2_42_2","doi-asserted-by":"publisher","DOI":"10.18653\/v1\/2022.naacl-main.272"},{"key":"e_1_3_2_43_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF01068419"},{"key":"e_1_3_2_44_2","volume-title":"Thirty-Fifth Conference on Neural Information Processing Systems Datasets and Benchmarks Track (Round 2)","author":"Thakur Nandan","year":"2021","unstructured":"Nandan Thakur, Nils Reimers, Andreas R\u00fcckl\u00e9, Abhishek Srivastava, and Iryna Gurevych. 2021. BEIR: A heterogeneous benchmark for zero-shot evaluation of information retrieval models. In Thirty-Fifth Conference on Neural Information Processing Systems Datasets and Benchmarks Track (Round 2)."},{"key":"e_1_3_2_45_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-20161-5_54"},{"key":"e_1_3_2_46_2","doi-asserted-by":"publisher","DOI":"10.1145\/3459637.3482162"},{"key":"e_1_3_2_47_2","volume-title":"International Conference on Learning Representations","author":"Xiong Lee","year":"2020","unstructured":"Lee Xiong, Chenyan Xiong, Ye Li, Kwok-Fung Tang, Jialin Liu, Paul N. Bennett, Junaid Ahmed, and Arnold Overwijk. 2020. Approximate nearest neighbor negative contrastive learning for dense text retrieval. In International Conference on Learning Representations."},{"key":"e_1_3_2_48_2","article-title":"XLNet: Generalized autoregressive pretraining for language understanding","volume":"32","author":"Yang Zhilin","year":"2019","unstructured":"Zhilin Yang, Zihang Dai, Yiming Yang, Jaime Carbonell, Russ R. Salakhutdinov, and Quoc V. Le. 2019. XLNet: Generalized autoregressive pretraining for language understanding. Advances in Neural Information Processing Systems 32 (2019).","journal-title":"Advances in Neural Information Processing Systems"},{"key":"e_1_3_2_49_2","doi-asserted-by":"publisher","DOI":"10.1145\/3404835.3462880"},{"key":"e_1_3_2_50_2","doi-asserted-by":"publisher","DOI":"10.1145\/3397271.3401325"},{"key":"e_1_3_2_51_2","article-title":"RepBERT: Contextualized text embeddings for first-stage retrieval","author":"Zhan Jingtao","year":"2020","unstructured":"Jingtao Zhan, Jiaxin Mao, Yiqun Liu, Min Zhang, and Shaoping Ma. 2020. RepBERT: Contextualized text embeddings for first-stage retrieval. arXiv preprint arXiv:2006.15498 (2020).","journal-title":"arXiv preprint arXiv:2006.15498"}],"container-title":["ACM Transactions on Information Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3639818","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3639818","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T00:03:50Z","timestamp":1750291430000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3639818"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,4,29]]},"references-count":50,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2024,9,30]]}},"alternative-id":["10.1145\/3639818"],"URL":"https:\/\/doi.org\/10.1145\/3639818","relation":{},"ISSN":["1046-8188","1558-2868"],"issn-type":[{"value":"1046-8188","type":"print"},{"value":"1558-2868","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,4,29]]},"assertion":[{"value":"2023-03-15","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2023-12-21","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2024-04-29","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}