Elamur Research⌕
☰
home / papers / 2021 / COIL: Revisit Exact Lexical Match in Information Retrieval with Contextualized Inverted List

COIL: Revisit Exact Lexical Match in Information Retrieval with Contextualized Inverted List

Paper · 2021 · Luyu Gao, Zhuyun Dai and Jamie Callan

Summary

Classical retrievers such as BM25 search efficiently through inverted lists, but they score matching terms with frequency statistics that ignore meaning. As a result, they cannot distinguish the senses of a word, such as "bank" of a river versus a financial bank. Neural retrievers fix this with soft matching across all query and document terms, but they give up the efficiency of exact-match search.

The authors propose COIL (COntextualized Inverted List), which keeps exact token overlap as the matching criterion. Each document token is encoded offline with a Transformer LM, and the resulting contextualized vector is stored in that token's inverted list instead of term statistics. At query time, each query token looks up only its own list and scores documents by vector similarity. COIL-tok uses token matching alone, while COIL-full adds a CLS-vector match to handle vocabulary mismatch.

On large ad hoc retrieval benchmarks built on MS MARCO, COIL beats classical lexical and deep-LM-augmented lexical retrievers. It also beats dense retrievers such as DPR at similar or lower latency. This suggests exact-match retrieval still has substantial room for improvement.

Key points

  • Scoring is computed only over query–document overlapping tokens, using similarity of their contextualized vectors. The CLS match in COIL-full addresses vocabulary mismatch, while contextualization handles semantic mismatch.
  • On TREC DL 2019 queries, the extracted results table shows COIL variants at about 0.66–0.70 NDCG@10, compared with roughly 0.51 for BM25 and about 0.64 for the strongest dense baseline. Exact row-to-system mapping could not be fully verified from the extracted table.
  • Reducing COIL-full's CLS dimension from 768 to 128 and shrinking token dimensions cuts GPU latency from about 41 ms to about 16 ms. COIL-tok runs within the same order of magnitude as BM25 (36 ms on CPU) and faster than DPR (293 ms CPU / 32 ms GPU).
  • All COIL configurations are faster than the reported ColBERT latency of about 458 ms, even without approximate search or quantization. COIL also avoids ColBERT's single huge all-token index.
  • A case study shows COIL separating word senses, for example government "cabinet" versus furniture, and even scoring stop words like "is" differently by context. Code is available at github.com/luyug/COIL.

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

 Institutions

🎓Carnegie Mellon UniversityPittsburgh · United States365 works · 158,048 citations

📚 Shelves 5The field of science this work belongs to (OpenAlex fields).Computer Science · 9,086 worksArtificial Intelligence · 8,889 worksArts and Humanities · 9,296 worksLanguage and Linguistics · 9,206 worksInformation Systems · 523 works

🧭 Topics 1Research subjects and languages the work is about.Information retrieval & search · 145 works

Cite

Cite as Luyu Gao, Zhuyun Dai and Jamie Callan. 2021. COIL: Revisit Exact Lexical Match in Information Retrieval with Contextualized Inverted List. Proceedings of the 2021 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies.

The paper itself, not this page. BibTeX from the library's record of the work. DOI 10.18653/v1/2021.naacl-main.241

@inproceedings{gao2021coil,
  title = {{COIL: Revisit Exact Lexical Match in Information Retrieval with Contextualized Inverted List}},
  author = {Luyu Gao, Zhuyun Dai and Jamie Callan},
  booktitle = {Proceedings of the 2021 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies},
  year = {2021},
  doi = {10.18653/v1/2021.naacl-main.241},
  url = {https://doi.org/10.18653/v1/2021.naacl-main.241}
}

References

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

  1. S. Blackford, J. Demmel, J. Dongarra, I. Duff, S. Hammarling, Greg Henry, M. Héroux, L. Kaufman, Andrew Lumsdaine, A. Petitet, R. Pozo, K. Remington, and C. Whaley. 2002. An updated set of basic linear algebra subprograms (blas). ACM Transactions on Mathematical Software, 28. find
  2. Nick Craswell, Bhaskar Mitra, Emine Yilmaz, Daniel Campos, and Ellen M Voorhees. 2020. Overview of the trec 2019 deep learning track. arXiv preprint arXiv:2003.07820.
  3. Zhuyun Dai and J. Callan. 2019a. Context-aware sentence/passage term importance estimation for first stage retrieval. ArXiv, abs/1910.10687. — [arXiv:1910.10687](https://arxiv.org/abs/1910.10687) find
  4. Zhuyun Dai and J. Callan. 2020. Context-aware document term weighting for ad-hoc search. Proceedings of The Web Conference 2020. find
  5. Zhuyun Dai and Jamie Callan. 2019b. Deeper text understanding for IR with contextual neural language modeling. In Proceedings of the 42nd International ACM SIGIR Conference on Research and Development in Information Retrieval, SIGIR 2019, Paris, France, July 21-25, 2019, pages 985–988. ACM. find
  6. ECIR 2021, Virtual Event, March 28 - April 1, 2021, Proceedings, Part I. find
  7. J. Guo, Y. Fan, Qingyao Ai, and W. Croft. 2016. A deep relevance matching model for ad-hoc retrieval. Proceedings of the 25th ACM International on Conference on Information and Knowledge Management. find
  8. R. Guo, Philip Y. Sun, E. Lindgren, Quan Geng, David Simcha, Felix Chern, and S. Kumar. 2019. Accelerating large-scale inference with anisotropic vector quantization. arXiv: Learning. find
  9. Charles R. Harris, K. Jarrod Millman, Stéfan J van der Walt, Ralf Gommers, Pauli Virtanen, David Cournapeau, Eric Wieser, Julian Taylor, Sebastian Berg, Nathaniel J. Smith, Robert Kern, Matti Picus, Stephan Hoyer, Marten H. van Kerkwijk, Matthew Brett, Allan Haldane, Jaime Fernández del Río, Mark Wi…
  10. J. Devlin, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova. 2019. Bert: Pre-training of deep bidirectional transformers for language understanding. In NAACL-HLT.
  11. 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. find
  12. Fernando Diaz, Bhaskar Mitra, and Nick Craswell. 2016. Query expansion with locally-trained word embeddings. In Proceedings of the 54th Annual Meeting of the Association for Computational Linguistics. find
  13. Samuel Humeau, Kurt Shuster, Marie-Anne Lachaux, and J. Weston. 2020. Poly-encoders: Architectures and pre-training strategies for fast and accurate multi-sentence scoring. In ICLR. find
  14. Debasis Ganguly, Dwaipayan Roy, Mandar Mitra, and Gareth J. F. Jones. 2015. Word embedding based generalized language model for information retrieval. In Proceedings of the 38th International ACM SIGIR Conference on Research and Development in Information Retrieval. find
  15. Luyu Gao, Zhuyun Dai, and Jamie Callan. 2020. Modularized transfomer-based ranking framework. In Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing, EMNLP 2020, Online, November 16-20, 2020. Association for Computational Linguistics. find
  16. Luyu Gao, Zhuyun Dai, and Jamie Callan. 2021a. Rethink training of BERT rerankers in multi-stage retrieval pipeline. In Advances in Information Retrieval - 43rd European Conference on IR Research, ECIR 2021, Virtual Event, March 28 - April 1, 2021, Proceedings, Part II. find
  17. Luyu Gao, Zhuyun Dai, Tongfei Chen, Zhen Fan, Benjamin Van Durme, and Jamie Callan. 2021b. Complement lexical retrieval model with semantic residual embeddings. In Advances in Information Retrieval - 43rd European Conference on IR Research, J. Johnson, M. Douze, and H. Jégou. 2017. Billion-scale sim…
  18. V. Karpukhin, Barlas Oğuz, Sewon Min, Patrick Lewis, Ledell Yu Wu, Sergey Edunov, Danqi Chen, and W. Yih. 2020. Dense passage retrieval for open-domain question answering. ArXiv, abs/2004.04906.
  19. O. Khattab and M. Zaharia. 2020. Colbert: Efficient and effective passage search via contextualized late interaction over bert. Proceedings of the 43rd International ACM SIGIR Conference on Research and Development in Information Retrieval.
  20. Yoon Kim. 2014. Convolutional neural networks for sentence classification. In EMNLP.
  21. John Lafferty and Chengxiang Zhai. 2001. Document language models, query models, and risk minimization for information retrieval. In Proceedings of the 24th Annual International ACM SIGIR Conference on Research and Development in Information Retrieval. find
  22. Victor Lavrenko and W. Bruce Croft. 2001. Relevance-based language models. In Proceedings of the 24th Annual International ACM SIGIR Conference on Research and Development in Information Retrieval. model for probabilistic weighted retrieval. In Proceedings of the 17th Annual International ACM-SIGIR… find
  23. Y. Liu, Myle Ott, Naman Goyal, Jingfei Du, Mandar Joshi, Danqi Chen, Omer Levy, M. Lewis, Luke Zettlemoyer, and Veselin Stoyanov. 2019. Roberta: A robustly optimized bert pretraining approach. ArXiv, abs/1907.11692. find
  24. Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N. Gomez, L. Kaiser, and Illia Polosukhin. 2017. Attention is all you need. In NIPS.
  25. Yi Luan, Jacob Eisenstein, Kristina Toutanova, and M. Collins. 2020. Sparse, dense, and attentional representations for text retrieval. ArXiv, abs/2005.00181.
  26. Sean MacAvaney, F. Nardini, R. Perego, N. Tonellotto, Nazli Goharian, and O. Frieder. 2020. Efficient document re-ranking for transformers by precomputing term representations. Proceedings of the 43rd International ACM SIGIR Conference on Research and Development in Information Retrieval. find
  27. Donald Metzler and W. Bruce Croft. 2005. A markov random field model for term dependencies. In SIGIR 2005: Proceedings of the 28th Annual International ACM SIGIR Conference on Research and Development in Information Retrieval. find
  28. Tomas Mikolov, Ilya Sutskever, Kai Chen, G. S. Corrado, and J. Dean. 2013. Distributed representations of words and phrases and their compositionality. In NIPS.
  29. Rodrigo Nogueira and Kyunghyun Cho. 2019. Passage re-ranking with bert. ArXiv, abs/1901.04085.
  30. Rodrigo Nogueira and Jimmy Lin. 2019. doc2query to doctttttquery. find
  31. Thomas Wolf, Lysandre Debut, Victor Sanh, Julien Chaumond, Clement Delangue, Anthony Moi, Pier-ric Cistac, Tim Rault, Rémi Louf, Morgan Funtowicz, Joe Davison, Sam Shleifer, Patrick von Platen, Clara Ma, Yacine Jernite, Julien Plu, Canwen Xu, Teven Le Scao, Sylvain Gugger, Mariama Drame, Quentin Lho…
  32. Chenyan Xiong, Zhuyun Dai, J. Callan, Zhiyuan Liu, and R. Power. 2017. End-to-end neural ad-hoc ranking with kernel pooling. Proceedings of the 40th International ACM SIGIR Conference on Research and Development in Information Retrieval. find
  33. Lee Xiong, Chenyan Xiong, Ye Li, Kwok-Fung Tang, J. Liu, P. Bennett, Junaid Ahmed, and Arnold Overwijk. 2020. Approximate nearest neighbor negative contrastive learning for dense text retrieval. ArXiv, abs/2007.00808.
  34. Z. Yang, Zihang Dai, Yiming Yang, J. Carbonell, R. Salakhutdinov, and Quoc V. Le. 2019. Xlnet: Generalized autoregressive pretraining for language understanding. In NeurIPS.
  35. From Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, Alban Desmaison, Andreas Kopf, Edward Yang, Zachary DeVito, Martin Raison, Alykhan Te-jani, Sasank Chilamkurthy, Benoit Steiner, Lu Fang, Junjie Bai,…
  36. Jeffrey Pennington, R. Socher, and Christopher D. Manning. 2014. Glove: Global vectors for word representation. In EMNLP.
  37. Matthew E. Peters, Mark Neumann, Mohit Iyyer, Matt Gardner, Christopher Clark, Kenton Lee, and Luke Zettlemoyer. 2018. Deep contextualized word representations. ArXiv, abs/1802.05365.
  38. Stephen E Robertson and Steve Walker. 1994. Some simple effective approximations to the 2-poisson find

Updated

↑ back to top

This page in Markdown → https://md.research.elamur.ai/free/en/papers/gao-2021-coil-revisit-exact-lexical-match/