Elamur Research
☰
home / papers / 2020 / ColBERT: Efficient and Effective Passage Search via Contextualized Late Interaction over BERT

ColBERT: Efficient and Effective Passage Search via Contextualized Late Interaction over BERT

Written for the Research library (claude-opus-5-5) from the paper text, in our own words: the license "arXiv — non-exclusive licence to distribute" does not allow redistributing the text itself. Original — arxiv.org/pdf/2004.12832

Summary

BERT-based rankers greatly improved passage search, but they are very expensive to run. Each query–document pair has to go through the full transformer, so a single query can take seconds on a GPU. ColBERT addresses this with "late interaction". BERT encodes the query and each document separately into sets of per-token embeddings. Relevance is then scored with a light MaxSim step: every query token finds its most similar document token, and these maxima are added up. Because documents are encoded without the query, their embeddings can be computed and stored offline. The query is encoded only once per search. The same scoring also works with vector-similarity indexes, so ColBERT can either re-rank BM25 candidates or retrieve end-to-end from the whole collection. The authors test it on MS MARCO and TREC CAR. Its accuracy is close to existing BERT rankers and better than every non-BERT baseline, while it is about two orders of magnitude faster. This makes neural ranking with pretrained LMs practical at production latencies.

Key points

  • In re-ranking mode, ColBERT is over 170× faster than earlier BERT rankers and needs about 14,000× fewer FLOPs per query. Its main model reaches MRR@10 of 34.9% on the MS MARCO dev set.
  • End-to-end retrieval improves both MRR@10 and recall over re-ranking BM25 output. ColBERT's Recall@50 is higher than the official BM25 Recall@1000.
  • Ablations on a 5-layer BERT variant show that each part matters: a single-vector [CLS] dot-product model, swapping MaxSim for average similarity, and removing query augmentation all lower MRR@10.
  • Indexing the roughly 9M-passage MS MARCO collection takes about 3 hours on one server with four GPUs, because each document goes through BERT only once.
  • Storage can drop from 286 GiB to 27 GiB by using 24-dimensional embeddings stored as 2-byte floats, at a cost of about 1 point of MRR@10.

Our summary of the paper, in our own words — not its text. The work belongs to its authors; read it at the links above.

Fields: Computing & GPUs

Cited by

526 papers of our library cite it (of the 140673 whose bibliographies we read); 22 of them have a page here, 504 not yet.

Cite

The paper itself, not this page. BibTeX from the library's record of the work. DOI 10.1145/3397271.3401075 · arXiv 2004.12832

@inproceedings{khattab2020colbert,
  title = {{ColBERT: Efficient and Effective Passage Search via Contextualized Late Interaction over BERT}},
  author = {Khattab, Omar and Zaharia, Matei},
  booktitle = {SIGIR 2020},
  year = {2020},
  doi = {10.1145/3397271.3401075},
  eprint = {2004.12832},
  archivePrefix = {arXiv},
  url = {https://doi.org/10.1145/3397271.3401075}
}

References

42 references, 6 of them with a card of ours. ↗ leads to the work, «find» searches for one we have no id for yet.

  1. Firas Abuzaid, Geet Sethi, Peter Bailis, and Matei Zaharia. 2019. To Index or Not to Index: Optimizing Exact Maximum Inner Product Search. In 2019 IEEE 35th International Conference on Data Engineering (ICDE). IEEE, 1250–1261. find
  2. Zhuyun Dai and Jamie Callan. 2019. Context-Aware Sentence/Passage Term Importance Estimation For First Stage Retrieval. arXiv preprint arXiv:1910.10687 (2019). — [arXiv:1910.10687](https://arxiv.org/abs/1910.10687) find
  3. Zhuyun Dai and Jamie Callan. 2019. Deeper Text Understanding for IR with Contextual Neural Language Modeling. arXiv preprint arXiv:1905.09217 (2019). — [arXiv:1905.09217](https://arxiv.org/abs/1905.09217) find
  4. Zhuyun Dai, Chenyan Xiong, Jamie Callan, and Zhiyuan Liu. 2018. Convolutional neural networks for soft-matching n-grams in ad-hoc search. In Proceedings of the eleventh ACM international conference on web search and data mining. 126–134. find
  5. 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). find
  6. Laura Dietz, Manisha Verma, Filip Radlinski, and Nick Craswell. 2017. TREC Complex Answer Retrieval Overview.. In TREC. find
  7. Jiafeng Guo, Yixing Fan, Qingyao Ai, and W Bruce Croft. 2016. A deep relevance matching model for ad-hoc retrieval. In Proceedings of the 25th ACM International on Conference on Information and Knowledge Management. ACM, 55–64. find
  8. Jiafeng Guo, Yixing Fan, Liang Pang, Liu Yang, Qingyao Ai, Hamed Zamani, Chen Wu, W Bruce Croft, and Xueqi Cheng. 2019. A deep look into neural ranking models for information retrieval. arXiv preprint arXiv:1903.06902 (2019). — [arXiv:1903.06902](https://arxiv.org/abs/1903.06902) find
  9. Sebastian Hofstätter and Allan Hanbury. 2019. Let’s measure run time! Extending the IR replicability infrastructure to include performance aspects. arXiv preprint arXiv:1907.04614 (2019). — [arXiv:1907.04614](https://arxiv.org/abs/1907.04614) find
  10. Sebastian Hofstätter, Navid Rekabsaz, Carsten Eickhoff, and Allan Hanbury. 2019. On the effect of low-frequency terms on neural-IR models. In Proceedings of the 42nd International ACM SIGIR Conference on Research and Development in Information Retrieval. 1137–1140. find
  11. Sebastian Hofstätter, Markus Zlabinger, and Allan Hanbury. 2019. TU Wien@ TREC Deep Learning’19–Simple Contextualization for Re-ranking. arXiv preprint arXiv:1912.01385 (2019). — [arXiv:1912.01385](https://arxiv.org/abs/1912.01385) find
  12. Po-Sen Huang, Xiaodong He, Jianfeng Gao, Li Deng, Alex Acero, and Larry Heck. 2013. Learning deep structured semantic models for web search using clickthrough data. In Proceedings of the 22nd ACM international conference on Information & Knowledge Management. 2333–2338. find
  13. Shiyu Ji, Jinjin Shao, and Tao Yang. 2019. Efficient Interaction-based Neural Ranking with Locality Sensitive Hashing. In The World Wide Web Conference. ACM, 2858–2864. find
  14. Xiaoqi Jiao, Yichun Yin, Lifeng Shang, Xin Jiang, Xiao Chen, Linlin Li, Fang Wang, and Qun Liu. 2019. Tinybert: Distilling bert for natural language understanding. arXiv preprint arXiv:1909.10351 (2019). find
  15. Jeff Johnson, Matthijs Douze, and Hervé Jégou. 2017. Billion-scale similarity search with GPUs. arXiv preprint arXiv:1702.08734 (2017). find our card
  16. Diederik P Kingma and Jimmy Ba. 2014. Adam: A method for stochastic optimization. arXiv preprint arXiv:1412.6980 (2014). find
  17. Ron Kohavi, Alex Deng, Brian Frasca, Toby Walker, Ya Xu, and Nils Pohlmann. 2013. Online controlled experiments at large scale. In SIGKDD. find
  18. Sean MacAvaney, Andrew Yates, Arman Cohan, and Nazli Goharian. 2019. Cedr: Contextualized embeddings for document ranking. In Proceedings of the 42nd International ACM SIGIR Conference on Research and Development in Information Retrieval. ACM, 1101–1104. find
  19. Paul Michel, Omer Levy, and Graham Neubig. 2019. Are Sixteen Heads Really Better than One?. In Advances in Neural Information Processing Systems. 14014– 14024. find our card
  20. Bhaskar Mitra and Nick Craswell. 2019. An Updated Duet Model for Passage Re-ranking. arXiv preprint arXiv:1903.07666 (2019). — [arXiv:1903.07666](https://arxiv.org/abs/1903.07666) find
  21. Bhaskar Mitra, Nick Craswell, et al. 2018. An introduction to neural information retrieval. Foundations and Trends® in Information Retrieval 13, 1 (2018), 1–126. find
  22. Bhaskar Mitra, Fernando Diaz, and Nick Craswell. 2017. Learning to match using local and distributed representations of text for web search. In Proceedings of the 26th International Conference on World Wide Web. International World Wide Web Conferences Steering Committee, 1291–1299. find
  23. Bhaskar Mitra, Corby Rosset, David Hawking, Nick Craswell, Fernando Diaz, and Emine Yilmaz. 2019. Incorporating query term independence assumption for efficient retrieval and ranking using deep neural networks. arXiv preprint arXiv:1907.03693 (2019). — [arXiv:1907.03693](https://arxiv.org/abs/1907.03693) find
  24. Tri Nguyen, Mir Rosenberg, Xia Song, Jianfeng Gao, Saurabh Tiwary, Rangan Majumder, and Li Deng. 2016. MS MARCO: A Human-Generated MAchine Reading COmprehension Dataset. (2016). find our card
  25. Rodrigo Nogueira and Kyunghyun Cho. 2019. Passage Re-ranking with BERT. arXiv preprint arXiv:1901.04085 (2019). find our card
  26. Rodrigo Nogueira, Jimmy Lin, and AI Epistemic. 2019. From doc2query to docTTTTTquery. (2019). find
  27. Rodrigo Nogueira, Wei Yang, Kyunghyun Cho, and Jimmy Lin. 2019. Multi-Stage Document Ranking with BERT. arXiv preprint arXiv:1910.14424 (2019). — [arXiv:1910.14424](https://arxiv.org/abs/1910.14424) find
  28. Rodrigo Nogueira, Wei Yang, Jimmy Lin, and Kyunghyun Cho. 2019. Document Expansion by Query Prediction. arXiv preprint arXiv:1904.08375 (2019). find our card
  29. Matthew E Peters, Mark Neumann, Mohit Iyyer, Matt Gardner, Christopher Clark, Kenton Lee, and Luke Zettlemoyer. 2018. Deep contextualized word representations. arXiv preprint arXiv:1802.05365 (2018). find
  30. Yifan Qiao, Chenyan Xiong, Zhenghao Liu, and Zhiyuan Liu. 2019. Understanding the Behaviors of BERT in Ranking. arXiv preprint arXiv:1904.07531 (2019). — [arXiv:1904.07531](https://arxiv.org/abs/1904.07531) find
  31. 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). find
  32. Stephen E Robertson, Steve Walker, Susan Jones, Micheline M Hancock-Beaulieu, Mike Gatford, et al. 1995. Okapi at TREC-3. NIST Special Publication (1995). find our card
  33. Raphael Tang, Yao Lu, Linqing Liu, Lili Mou, Olga Vechtomova, and Jimmy Lin. 2019. Distilling task-specific knowledge from BERT into simple neural networks. arXiv preprint arXiv:1903.12136 (2019). — [arXiv:1903.12136](https://arxiv.org/abs/1903.12136) find
  34. Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Lukasz Kaiser, and Illia Polosukhin. 2017. Attention is all you need. In Advances in neural information processing systems. 5998–6008. find
  35. Yonghui Wu, Mike Schuster, Zhifeng Chen, Quoc V Le, Mohammad Norouzi, Wolfgang Macherey, Maxim Krikun, Yuan Cao, Qin Gao, Klaus Macherey, et al. 2016. Google’s neural machine translation system: Bridging the gap between human and machine translation. arXiv preprint arXiv:1609.08144 (2016). find
  36. Chenyan Xiong, Zhuyun Dai, Jamie Callan, Zhiyuan Liu, and Russell Power. 2017. End-to-end neural ad-hoc ranking with kernel pooling. In Proceedings of the 40th International ACM SIGIR conference on research and development in information retrieval. 55–64. find
  37. Peilin Yang, Hui Fang, and Jimmy Lin. 2018. Anserini: Reproducible ranking baselines using Lucene. Journal of Data and Information Quality (JDIQ) 10, 4 (2018), 1–20. find
  38. Wei Yang, Kuang Lu, Peilin Yang, and Jimmy Lin. 2019. Critically Examining the” Neural Hype” Weak Baselines and the Additivity of Effectiveness Gains from Neural Ranking Models. In Proceedings of the 42nd International ACM SIGIR Conference on Research and Development in Information Retrieval. 1129–1… find
  39. Zeynep Akkalyoncu Yilmaz, Wei Yang, Haotian Zhang, and Jimmy Lin. 2019. Cross-domain modeling of sentence-level evidence for document retrieval. In Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Pr… find
  40. Ofir Zafrir, Guy Boudoukh, Peter Izsak, and Moshe Wasserblat. 2019. Q8bert: Quantized 8bit bert. arXiv preprint arXiv:1910.06188 (2019). — [arXiv:1910.06188](https://arxiv.org/abs/1910.06188) find
  41. Hamed Zamani, Mostafa Dehghani, W Bruce Croft, Erik Learned-Miller, and Jaap Kamps. 2018. From neural re-ranking to neural ranking: Learning a sparse representation for inverted indexing. In Proceedings of the 27th ACM International Conference on Information and Knowledge Management. ACM, 497–506. find
  42. Le Zhao. 2012. Modeling and solving term mismatch for full-text retrieval. Ph.D. Dissertation. Carnegie Mellon University. find