Seismic: A Novel Inverted Index for Fast Approximate Retrieval with Learned Sparse Representations

In the world of information retrieval, learned sparse representations have emerged as a powerful tool for text embedding. These models are effective at capturing relevance and are inherently interpretable, making them an attractive choice for many applications. However, integrating these embeddings into traditional inverted indexes poses significant challenges due to their distributional differences from term frequency-based models like BM25. Recognizing this gap, researchers Sebastian Bruch, Franco Maria Nardini, Cosimo Rulli, and Rossano Venturini have introduced Seismic, a novel organization of the inverted index that addresses these issues.

What Changed?

Seismic introduces a new way to organize inverted lists in an inverted index, specifically tailored for learned sparse representations. The key innovation is the use of geometrically-cohesive blocks, each with a summary vector. This structure allows for efficient approximate retrieval by quickly filtering out irrelevant blocks during query processing.

Why It Matters

For practitioners, this means:

• Faster Query Processing: Seismic achieves sub-millisecond per-query latency on various sparse embeddings of the MS MARCO dataset.
• High Recall: Despite the speed, it maintains high recall, ensuring that relevant documents are still retrieved accurately.
• Scalability: The method is one to two orders of magnitude faster than state-of-the-art inverted index-based solutions and outperforms graph-based methods used in the BigANN Challenge at NeurIPS 2023.

Technical Details

Architecture

• Geometrically-Cohesive Blocks: Inverted lists are grouped into blocks where each block contains summary vectors. These summaries help in quickly determining if a block needs to be evaluated during query processing.
• Summary Vectors: Each block has a summary vector that captures the essence of the documents within it. This vector is used to filter out irrelevant blocks, reducing the number of comparisons needed.

Query Processing

• Initial Filtering: During query processing, Seismic uses the summary vectors to quickly determine which blocks are likely to contain relevant documents.
• Detailed Evaluation: Only the blocks that pass the initial filtering are fully evaluated, significantly reducing the computational load.

Benchmarks

• MS MARCO Dataset: Experiments on the MS MARCO dataset show that Seismic can process queries in sub-millisecond times while maintaining high recall.
• Comparison with State-of-the-Art: Seismic outperforms existing inverted index-based methods by one to two orders of magnitude and surpasses graph-based methods from the BigANN Challenge.

Implementation Notes

• Single-Threaded Performance: The method is designed to be efficient even in a single-threaded environment, making it suitable for resource-constrained systems.
• Scalability: The geometrically-cohesive block structure scales well with increasing dataset sizes, ensuring that performance remains high as the index grows.

Conclusion

Seismic represents a significant step forward in the integration of learned sparse representations into inverted indexes. By addressing the challenges posed by the distributional differences between these embeddings and traditional models, it enables fast and effective approximate retrieval. For practitioners working on large-scale text retrieval systems, Seismic offers a promising solution that balances speed and accuracy.