Seismic: Efficient and Effective Retrieval over Learned Sparse Representation

Sebastian Bruch, Franco Maria Nardini, Cosimo Rulli, Rossano VenturiniIIR 2024 · OpenReview

Abstract

Learned Sparse Retrieval (LSR) models, such as SPLADE, have emerged as powerful tools for information retrieval, offering high interpretability and strong generalization. However, their deployment is often hindered by the inefficiency of traditional inverted indexes and the limitations of graph-based approximate nearest neighbor methods in high-sparsity regimes. We introduce SEISMIC (Spilled Clustering of Inverted Lists with Summaries for Maximum Inner Product Search), a retrieval algorithm specifically designed for the statistical and geometric properties of learned sparse embeddings. SEISMIC organizes inverted lists into cohesive blocks and utilizes summary vectors for efficient dynamic pruning. Experimental results on MS MARCO and Natural Questions datasets show that SEISMIC provides up to a 21.6x speedup over state-of-the-art competitors while maintaining competitive accuracy.

Introduction

Modern search systems are increasingly adopting Learned Sparse Retrieval (LSR) models. Unlike traditional keyword-based methods like BM25, LSR models leverage Large Language Models to transform text into high-dimensional sparse vectors. While these models excel in capturing semantic nuances, they present a challenge for standard retrieval infrastructures. Traditional inverted indexes are optimized for simple keyword matching, not the complex weight distributions of neural embeddings. Conversely, graph-based Approximate Nearest Neighbor (ANN) methods, though fast for dense vectors, often underperform when query vectors are highly sparse. SEISMIC addresses these challenges by reimagining the inverted index structure to exploit the geometric relationships inherent in learned embeddings.

Methodology

The SEISMIC framework is built upon four core components designed to minimize the search space without sacrificing retrieval quality:

  1. Static Pruning: To manage the scale of the index, SEISMIC retains only the top $\lambda$ most significant documents for each term in the vocabulary.
  2. Clustering-based Blocking: Rather than treating inverted lists as flat structures, SEISMIC partitions them into $\beta$ geometrically-cohesive blocks using a shallow K-Means approach. This grouping ensures that similar documents are processed together.
  3. Summary Vectors: Each block is represented by a "summary vector" or sketch. This vector is constructed to serve as a conservative upper bound for the inner product scores of all documents within the block.
  4. Dynamic Pruning: At query time, the system evaluates the summary vector first. If the upper bound score for a block cannot exceed the current threshold in the results heap, the entire block is bypassed.
Algorithms for indexing and query processing in SEISMIC.

Experimental Evaluation

We evaluated SEISMIC on two benchmark datasets: MS MARCO v1 Passage and Natural Questions (NQ), using embeddings from SPLADE and E-SPLADE models. We compared SEISMIC against leading competitors, including PyAnn and GrassRMA, which were top performers in the 2023 BigANN Challenge.

Results and Discussion

SEISMIC demonstrates substantial performance gains across all tested scenarios. As shown in the results table, SEISMIC achieves massive speedups, particularly on the E-SPLADE MS MARCO benchmark, where it outperformed PyAnn and GrassRMA by up to 21.6x.

Performance comparison of SEISMIC against baselines on MS MARCO and NQ datasets.

A key finding is that SEISMIC's advantage over graph-based methods increases as query sparsity grows. While graph traversals can become inefficient in sparse spaces, SEISMIC’s coordinate-at-a-time approach remains robust. Furthermore, SEISMIC maintains high precision; at a 97% accuracy level on E-SPLADE, it evaluated only 2,198 documents compared to the ~40,000 required by PyAnn.

Conclusion

SEISMIC represents a significant advancement in efficient retrieval for learned sparse representations. By combining clustering-based blocking with conservative summary vectors, it enables aggressive pruning that far exceeds the performance of current state-of-the-art methods. Future work will focus on further reducing the memory footprint through advanced compression and quantization of the index structures.

Summary updated

BibTeX
@inproceedings{bruch2024seismic,
  author = {Sebastian Bruch and Franco Maria Nardini and Cosimo Rulli and Rossano Venturini},
  title = {{Seismic: Efficient and Effective Retrieval over Learned Sparse Representation}},
  booktitle = {IIR},
  year = {2024},
  url = {https://openreview.net/forum?id=Syvk3r99hi},
}
Figure