Sparse, Dense, and Attentional Representations for Text Retrieval

Yi Luan, Jacob Eisenstein, Kristina Toutanova, Michael Collins

TL;DR

This paper investigates why standard dense "dual encoders" (like BERT-based retrievers) often struggle with long documents compared to classical sparse models like BM25. The authors propose Multi-Vector Encodings (ME-BERT) and sparse-dense hybrids that bridge the gap between efficient dual encoders and expensive cross-attentional models, setting new state-of-the-art results on major retrieval benchmarks.

What Problem Does This Paper Address?

In modern information retrieval, there is a tug-of-war between efficiency and expressivity.

  1. Sparse models (BM25): Excellent at precise keyword matching but fail to capture synonyms or semantic meaning.
  2. Dual Encoders (Dense): Map queries and documents into a single fixed-length vector. They are fast (using Approximate Nearest Neighbor search) and capture semantics, but they struggle with "fidelity"—the ability to distinguish between documents when precise term overlap is required, especially as document length increases.
  3. Cross-Attention Models: Highly accurate because they look at every word in the query against every word in the document, but they are far too slow to search through millions of candidates.

The authors ask: Why do dual encoders fail on long documents, and can we build a model that has the speed of a dual encoder but the precision of an attentional model?

Methods

The authors approach the problem through both theoretical analysis and architectural innovation:

  • Fidelity Analysis: Using the theory of dimensionality reduction (specifically random projections), they prove that the "normalized margin" (the gap between a relevant document's score and its competitors) shrinks as documents get longer. To maintain the same retrieval quality, the embedding dimension must grow with document length.
  • Multi-Vector Encoding (ME-BERT): Instead of squeezing a whole document into one vector, ME-BERT represents a document as a set of $m$ vectors (e.g., the first 8 token embeddings). The relevance score is the maximum inner product between the query vector and any of the document's $m$ vectors. This allows for more "capacity" to store different aspects of a long document.
  • Sparse-Dense Hybrids: They propose a simple linear combination of scores from a sparse model (BM25) and their dense multi-vector model to get the best of both worlds: exact term matching and semantic generalization.

Datasets

The models were evaluated on several high-profile benchmarks:

  • MS MARCO (Passage and Document): The industry standard for large-scale web search retrieval.
  • Natural Questions (NQ): A dataset of real Google search queries paired with Wikipedia passages.
  • TREC-CAR: Used for evaluating the theoretical "fidelity" of random projections.
  • Containing Passage ICT: A synthetic task created by the authors where the model must find a specific Wikipedia passage that contains a hidden query string.

Key Insights and Ideas

  • The Length-Capacity Bottleneck: The most significant "aha moment" is the proof that fixed-length encodings are fundamentally limited. As a document grows, a single vector becomes a "blurry" representation. To achieve the same "fidelity" as BM25, a dual encoder needs significantly more dimensions for a 400-word passage than a 50-word one.
  • Max-Pooling over Vectors: By using a max operation over multiple vectors, the model can implement a form of "local" attention. This is computationally efficient because it still allows for standard vector indexing (you just index $m$ vectors per document instead of one).
  • Fidelity vs. Generalization: Sparse models have high fidelity (they don't confuse "cat" with "dog") but low generalization. Dense models generalize well but have lower fidelity. The hybrid approach is not just a "trick" but a necessary architectural choice to cover both requirements of retrieval.

Key Results

  • MS MARCO: On the MS MARCO Passage task, ME-BERT achieved an MRR@10 of 0.334, significantly outperforming the standard BERT dual encoder (0.302).
  • Hybrid Superiority: Combining ME-BERT with BM25 (ME-HYBRID) pushed the score even further to 0.343, outperforming several complex "re-ranking" pipelines while remaining efficient enough for first-stage retrieval.
  • Document Retrieval: On the MS MARCO Document task (longer texts), the multi-vector approach showed even larger gains, confirming the theory that more vectors help with longer content.
  • Efficiency: While ME-BERT requires more storage (3x to 8x the index size), its inference time remains sub-linear, making it practical for real-world systems.

Limitations and Future Work

  • Index Size: The primary drawback of ME-BERT is the increased memory footprint. Storing 8 vectors per document instead of 1 increases the RAM requirements for the search index significantly.
  • Fixed Vector Selection: In this paper, the authors simply took the first $m$ tokens. Future work could explore more intelligent ways to select which parts of a document deserve their own vector (e.g., clustering or representative phrase selection).
  • End-to-End Hybrid Training: The hybrid models in this paper used a simple linear interpolation of pre-computed scores. Training a model to jointly optimize the sparse and dense components from the start remains an open area for improvement.

Summary updated

Abstract

Dual encoders perform retrieval by encoding documents and queries into dense low-dimensional vectors, scoring each document by its inner product with the query. We investigate the capacity of this architecture relative to sparse bag-of-words models and attentional neural networks. Using both theoretical and empirical analysis, we establish connections between the encoding dimension, the margin between gold and lower-ranked documents, and the document length, suggesting limitations in the capacity of fixed-length encodings to support precise retrieval of long documents. Building on these insights, we propose a simple neural model that combines the efficiency of dual encoders with some of the expressiveness of more costly attentional architectures, and explore sparse-dense hybrids to capitalize on the precision of sparse retrieval. These models outperform strong alternatives in large-scale retrieval.
BibTeX
@article{luan2021sparse,
  author = {Yi Luan and Jacob Eisenstein and Kristina Toutanova and Michael Collins},
  title = {{Sparse, Dense, and Attentional Representations for Text Retrieval}},
  journal = {Trans. Assoc. Comput. Linguistics},
  year = {2021},
  url = {https://openreview.net/forum?id=Llk7gw-I__},
}

Loading related content...

Figure