Graph based search speeds up learned sparse retrieval by two and a half times

Getting a GRIP on Graph-Based Search for Learned Sparse Retrieval

Information RetrievalDatabases

Summary

Searching large collections of documents quickly and accurately is a key problem in information retrieval. The usual approach uses inverted indexes that match keywords to documents, but some recent approaches use neural networks to find important keywords in a smarter way. Most people thought graph based search methods were slower for this task. The paper shows that by combining ideas from inverted indexes with graph search techniques, you can make graph based search much faster without losing accuracy. They built a system called GRIP, which is 2.5 times faster than the best known inverted index method on a big public dataset.

What this means in practice

  • For search engine developers: Build search systems that return relevant results faster by using combined graph and inverted index techniques for learned sparse embeddings.
  • For ecommerce platform engineers: Implement faster product search with better recall using graph based learned sparse retrieval optimized by GRIP.

Authors

Vihan Lakshman, Franco Maria Nardini, Cosimo Rulli, Rossano Venturini

Abstract

Learned sparse retrieval (LSR) has recently gained traction in the information retrieval community for the ability to combine the generalization capabilities of neural representations with the interpretability of keyword-based search. A number of recent works have demonstrated that inverted indexes, when appropriately modified for learned sparse embeddings, achieve state-of-the-art recall-latency tradeoffs for LSR, often outperforming graph-based indexes by substantial margins in latency at a fixed recall target. As a result, the community has generally concluded that graph-based approximate nearest neighbor (ANN) search is inferior to inverted indexes for LSR. This paper challenges this conventional wisdom. Our key insight is that, while applying standard graph-based ANN indexes out-of-the-box to sparse vectors leads to uncompetitive performance, we can overcome these shortcomings by infusing the strengths of inverted indexes into graph-based search. In particular, we introduce three techniques to accelerate graph-based LSR: (i) term-based entry point seeding, (ii) approximate routing via sparse sketching, and (iii) sparse partition-based graph construction. We combine these techniques into a new graph-based ANN system for LSR we call GRIP. On the MS MARCO v2 benchmark (138M passages) with SPLADE embeddings, GRIP achieves a $2.5\times$ latency improvement over Seismic, a state-of-the-art inverted index tailored for LSR, at 95\% recall@10. Ultimately, our results call into question the default choice of inverted indexes for deploying learned sparse retrieval.