Elamur Research
☰
home / papers / 2021 / Sparse, Dense, and Attentional Representations for Text Retrieval

Sparse, Dense, and Attentional Representations for Text Retrieval

Written for the Research library (claude-opus-5-5) from the paper text. Original — aclanthology.org/2021.tacl-1.20.pdf

Summary

Dual encoders map queries and documents to fixed-size dense vectors and rank documents by inner product. They scale well to very large collections, but they can fall behind plain sparse methods such as BM25, especially on long documents where exact term matching matters. The authors analyze this gap. In theory, they study how well compressed encodings can reproduce bag-of-words rankings, a property they call fidelity. Using random projections and Johnson–Lindenstrauss-style arguments, they show that the required embedding dimension depends on the normalized margin between the correct document and its competitors. Longer documents tend to shrink that margin. They test the theory by compressing BM25 on TREC-CAR. Building on this, they propose ME-BERT, which represents each document with several vectors. This keeps retrieval cheap while adding expressiveness. They also combine dense and sparse scores in simple hybrids. On MS MARCO passage and document ranking, TREC DL 2019 and Natural Questions, the hybrid multi-vector model is consistently at or near the top among efficient retrievers. The work shows when dense retrieval still needs sparse support.

Key points

  • On recall@1 over three million candidate passages, BM25 can beat a fine-tuned DE-BERT-768 dual encoder, and the advantage grows with passage length.
  • The bounds relate the projection dimension k to the normalized margin. For error rate β = .05, the bound is k* ≤ 8.76(ε²/2 − ε³/3)⁻¹. It was checked empirically on TREC-CAR over 40 values of k between 32 and 9472.
  • ME-BERT stores 3 vectors of size 1024 per document, while DE-BERT stores one. ME-BERT's index is about 3× larger than DE-BERT's 34.2GB, and indexing takes 3.02h versus 1.52h.
  • With ScaNN approximate search on 160 CPU cores, ME-BERT reaches higher MRR than DE-BERT at equal query time in the high-quality range.
  • Full cross-attention models remain best for reranking but are too slow for first-stage retrieval. Code is released in google-research/language (multivec).

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: Natural language processing

Cited by

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

Cite

The paper itself, not this page. BibTeX from the library's record of the work. DOI 10.1162/tacl_a_00369

@article{luan2021sparse,
  title = {{Sparse, Dense, and Attentional Representations for Text Retrieval}},
  author = {Luan, Yi and Eisenstein, Jacob and Toutanova, Kristina and Collins, Michael},
  journal = {Transactions of the Association for Computational Linguistics},
  year = {2021},
  doi = {10.1162/tacl\_a\_00369},
  url = {https://doi.org/10.1162/tacl_a_00369}
}

References

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

  1. Dimitris Achlioptas. 2003. Database-friendly random projections: Johnson-Lindenstrauss with binary coins. Journal of Computer and System Sciences, 66(4):671–687. DOI: https:// find
  2. Jacob Devlin, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova. 2019. BERT: Pre-training of deep bidirectional transformers for language understanding. In Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies. find
  3. Samuel Humeau, Kurt Shuster, Marie-Anne Lachaux, and Jason Weston. 2020. Poly-encoders: Transformer architectures and pre-training strategies for fast and accurate multi-sentence scoring. In Proceedings of the International Conference on Learning Representations (ICLR). find
  4. Laura Dietz, Ben Gamari, Jeff Dalton, and Nick Craswell. 2018. TREC complex answer retrieval overview. In Text REtrieval Conference (TREC). find
  5. Thathachar S. Jayram and David P. Woodruff. 2013. Optimal bounds for Johnson-Lindenstrauss transforms and streaming problems with subconstant error. ACM Transactions on Algorithms (TALG), 9(3):1–17. DOI: https://doi.org/10.1145 /2483699.2483706 find
  6. Luyu Gao, Zhuyun Dai, Zhen Fan, and Jamie Callan. 2020. Complementing lexical retrieval with semantic residual embedding. CoRR, abs/2004.13969. Version 1. — [arXiv:2004.13969](https://arxiv.org/abs/2004.13969) find
  7. William B. Johnson and Joram Lindenstrauss. 1984. Extensions of Lipschitz mappings into a Hilbert space. Contemporary Mathematics, 26(189–206):1. find
  8. Daniel Gillick, Sayali Kulkarni, Larry Lansing, Alessandro Presta, Jason Baldridge, Eugene Ie, and Diego Garcia-Olano. 2019. Learning dense representations for entity retrieval. In Proceedings of the 23rd Conference on Computational Natural Language Learning (CoNLL). DOI: https://doi.org/10.18653/v1… ↗
  9. Daniel Kane, Raghu Meka, and Jelani Nelson. 2011. Almost optimal explicit Johnson-Lindenstrauss families. Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques. find
  10. Jiafeng Guo, Yixing Fan, Qingyao Ai, and W. Bruce Croft. 2016a. A deep relevance matching model for ad-hoc retrieval. In Proceedings of the 25th ACM International on Conference on Information and Knowledge Management. find
  11. Ruiqi Guo, Sanjiv Kumar, Krzysztof Choromanski, and David Simcha. 2016b. Quantization based fast inner product search. In Proceedings of the International Conference on Artificial Intelligence and Statistics (AISTATS). find
  12. Ruiqi Guo, Philip Sun, Erik Lindgren, Quan Geng, David Simcha, Felix Chern, and Sanjiv Kumar. 2020. Accelerating large-scale inference with anisotropic vector quantization. In Proceedings of the 37th International Conference on Machine Learning. find
  13. 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 International Conference on Information and Knowledge Management (CIKM). DOI: https://doi.org/10.1145 /2505515.25… find
  14. Vladimir Karpukhin, Barlas Oguz, Sewon Min, Patrick Lewis, Ledell Wu, Sergey Edunov, Danqi Chen, and Wen-tau Yih. 2020. Dense passage retrieval for open-domain question answering. In Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP). DOI: https:// doi.org… find our card
  15. Omar Khattab and Matei Zaharia. 2020. Col-BERT. In Proceedings of the 43rd International ACM SIGIR Conference on Research and Development in Information Retrieval. DOI: https://doi.org/10.1145/3397271 .3401075 — [doi:10.1145/3397271](https://doi.org/10.1145/3397271) ↗
  16. Tom Kwiatkowski, Jennimaria Palomaki, Olivia Redfield, Michael Collins, Ankur Parikh, Chris Alberti, Danielle Epstein, Illia Polosukhin, Jacob Devlin, Kenton Lee, Kristina Toutanova, Llion Jones, Matthew Kelcey, Ming-Wei Chang, Andrew M. Dai, Jakob Uszkoreit, Quoc Le, and Slav Petrov. 2019. Natural… find our card
  17. DOI: Rodrigo Nogueira, Wei Yang, Kyunghyun Cho, and Jimmy Lin. 2019a. Multi-stage document ranking with BERT. CoRR, abs/1910.14424. https://doi.org/10.1162/tacl a 00276 — [doi:10.1162/tacl](https://doi.org/10.1162/tacl) ↗
  18. Cody Kwok, Oren Etzioni, and Daniel S. Weld. 2001. Scaling question answering to the web. ACM Transactions on Information Systems (TOIS), 19(3):242–262. DOI: https://doi.org/10.1145/502115 .502117 — [doi:10.1145/502115](https://doi.org/10.1145/502115) ↗
  19. Rodrigo Nogueira, Wei Yang, Jimmy Lin, and Kyunghyun Cho. 2019b. Document expansion by query prediction. CoRR, abs/1904.08375. find our card
  20. Nils Reimers and Iryna Gurevych. 2019. Sentence-BERT: Sentence embeddings using Siamese BERT-networks. In Proceedings of Empirical Methods in Natural Language Processing (EMNLP). DOI: https://doi.org /10.18653/v1/D19-1410 ↗
  21. Kasper Green Larsen and Jelani Nelson. 2017. Optimality of the Johnson-Lindenstrauss lemma. In 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS). DOI: https://doi.org/10.1109/FOCS .2017.64 — [doi:10.1109/focs](https://doi.org/10.1109/focs) ↗
  22. Stephen Robertson, and Hugo Zaragoza. 2009. The probabilistic relevance framework: BM25 and beyond. Foundations and Trends in Information Retrieval, 3(4):333–389. DOI: https://doi.org/10.1561/1500000019 ↗ our card
  23. Kenton Lee, Ming-Wei Chang, and Kristina Toutanova. 2019. Latent retrieval for weakly supervised open domain question answering. In Proceedings of the Association for Computational Linguistics (ACL). find our card
  24. Minjoon Seo, Jinhyuk Lee, Tom Kwiatkowski, Ankur Parikh, Ali Farhadi, and Hannaneh Hajishirzi. 2019. Real-time open-domain question answering with dense-sparse phrase index. In Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics. find
  25. Ji Ma, Ivan Korotkov, Yinfei Yang, Keith Hall, and Ryan T. McDonald. 2020. Zero-shot neural retrieval via domain-targeted synthetic query generation. CoRR, abs/2004.14503. — [arXiv:2004.14503](https://arxiv.org/abs/2004.14503) find
  26. Bhaskar Mitra and Nick Craswell. 2018. An introduction to neural information retrieval. Foundations and Trends R in Information Retrieval, 13(1):1–126. DOI: https://doi .org/10.1561/1500000061 — [doi:10.1561/1500000061](https://doi.org/10.1561/1500000061) find
  27. Karen Spärck Jones. 1972. A statistical interpretation of term specificity and its application in retrieval. Journal of Documentation, 28(1):11–21. DOI: https://doi.org/10 .1108/eb026526 find
  28. Karthik Narasimhan, Adam Yala, and Regina Barzilay. 2016. Improving information extraction by acquiring external evidence with reinforcement learning. In Proceedings of Empirical Methods in Natural Language Processing (EMNLP). DOI: https://doi .org/10.18653/v1/D16-1261 find
  29. Nishant Subramani, Samuel Bowman, and Kyunghyun Cho. 2019. Can unconditional language models recover arbitrary sentences? In Advances in Neural Information Processing Systems. find
  30. Santosh S. Vempala. 2004. The Random Projection Method, volume 65. American Mathematical Society. find
  31. 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. find our card
  32. Ellen M. Voorhees. 2001. The TREC question answering track. Natural Language Engineering, 7(4):361–378. DOI: https://doi .org/10.1017/S1351324901002789 — [doi:10.1017/s1351324901002789](https://doi.org/10.1017/s1351324901002789) find
  33. Rodrigo Nogueira and Kyunghyun Cho. 2019. Passage re-ranking with BERT. CoRR, abs /1901.04085. find our card
  34. John Wieting and Douwe Kiela. 2019. No training required: Exploring random encoders for sentence classification. In Proceedings of the International Conference on Learning Representations (ICLR). find
  35. Rodrigo Nogueira and Jimmy Lin. 2019. From doc2query to doctttttquery. https://github .com/castorini/docTTTTTquery Lee Xiong, Chenyan Xiong, Ye Li, Kwok-Fung Tang, Jialin Liu, Paul Bennett, Junaid Ahmed, and Arnold Overwijk. 2020. Approximate nearest neighbor negative contrastive learning for dense… find our card
  36. Ming Yan, Chenliang Li, Chen Wu, Bin Bi, Wei Wang, Jiangnan Xia, and Luo Si. 2020. IDST at TREC 2019 deep learning track: Deep cascade ranking with generation-based document expansion and pre-trained language modeling. In Text REtrieval Conference (TREC). find
  37. Peilin Yang, Hui Fang, and Jimmy Lin, New York, NY, USA. 2018a. Anserini: Reproducible ranking baselines using lucene. Journal of Data and Information Quality, 10(4). DOI: https://doi.org/10.1145/3239571 — [doi:10.1145/3239571](https://doi.org/10.1145/3239571) ↗
  38. Wei Yang, Haotian Zhang, and Jimmy Lin. 2019. Simple applications of BERT for ad hoc document retrieval. CoRR, abs/1903.10972. — [arXiv:1903.10972](https://arxiv.org/abs/1903.10972) find
  39. Proofs A.1 Lemma 1 k \< 2 exp(− ( ǫ 2 / 2 − ǫ 3 / 3)) . 2 find