PaperlayerView exact revision on arXiv

Source-linked AI summary

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

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

arXiv:2610.30425v1cs.IRcs.DB

TL;DR

Graph-based ANN search has generally been considered inferior to inverted indexes for learned sparse retrieval. GRIP combines graph search with inverted-index-inspired techniques. On MS MARCO v2, it outperforms Seismic in latency across fixed recall targets.

  • Problem

    Graph-based search has been considered inferior to inverted indexes for learned sparse retrieval, whose sparse structure can make graph traversal inefficient.

    Source: §1 · p. 1

  • Method

    GRIP combines graph search with term-based entry point seeding, sparse sketching for approximate routing, and sparse partition-based graph construction.

    Source: §1 · pp. 1–2

  • Results

    2.2–3.4× faster than Seismic on the 138M-passage MS MARCO v2 benchmark with SPLADE-CoCondenser embeddings at recall@10 targets from 90% to 98%.

    Source: §1 · p. 1, §5 · p. 7

  • Takeaways & Limitations

    These results call into question the default choice of inverted indexes for learned sparse retrieval.

    Source: §5 · p. 7

    On MS MARCO v2 with CoCondenser embeddings, GRIP uses almost double the space of Seismic, and its index takes longer to build.

    Source: §5 · p. 7, §4 · p. 7

Abstract

from arXiv · show

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.

1 Introduction

GRIP challenges the view that graph indexes are uncompetitive for learned sparse retrieval by bringing inverted-index strengths into graph search. On MS MARCO v2 with SPLADE-CoCondenser embeddings, it outperforms Seismic across fixed recall targets.

1 Introduction

  • 2.2–3.4× lower latency than Seismic on MS MARCO v2 with SPLADE-CoCondenser embeddings at recall@10 targets from 90% to 98%.Figure 1 reports this comparison across fixed recall targets.Source: Figure 1 · p. 1, §1 · p. 1
  • Term-based entry point seeding starts graph search from documents with the largest weights for the query’s highest-impact terms.GRIP precomputes high-weight documents for each vocabulary term, using the sparse embeddings themselves to select entry points.Source: §1 · p. 2
  • Approximate routing sketches each document to its R largest-magnitude components, traverses the graph on sketches, then reranks candidates using full vectors.Because learned sparse weights are non-negative, sketched scores are lower bounds on exact scores; sketching complements quantization by reducing components touched per distance computation.Source: §1 · p. 2
  • Standard search-based graph construction is costly for learned sparse vectors: HNSW requires a beam width of 2000 for competitive search quality, roughly an order of magnitude increasing construction time.The paper estimates several days to build the MS MARCO v2 graph with this approach.Source: §1 · p. 2
  • Sparse PiPNN replaces wasteful dense matrix multiplication within partitions with inner products computed from a small inverted index.A refinement pass has each document search the finished graph from its own term seeds; construction falls from 5.5 hours to 47 minutes on MS MARCO v1 and takes 7.3 hours for MS MARCO v2.Source: §1 · pp. 2–3

2 Related Work

Learned sparse embeddings generalize lexical matching through sparse neural representations, while LSR indexing research has moved from early graph approaches to specialized inverted indexes. GRIP is differentiated by incorporating inverted-index structure into graph search.

2.1 Learned Sparse Embeddings

  • Learned sparse representations use high-dimensional vectors with few nonzero components, where each component represents a generalized concept rather than a fixed word.SPLADE is an influential family of learned sparse embedding models, and SPARSEUP is described as a newer model with improved retrieval quality over SPLADE.Source: §2.1 · p. 3

2.2 Algorithms for Learned Sparse Retrieval

  • Early LSR indexing work found that learned sparse term distributions differ from bag-of-words Zipfian distributions, making traditional text inverted indexes inefficient.The cited work motivates specialized search techniques for learned sparse representations.Source: §2.2 · p. 3
  • PyANNS and GrassRMA used HNSW with low-level optimizations, but did not incorporate inverted-index structure into graph search.Both were winners in the learned sparse retrieval track of the NeurIPS 2023 Big ANN benchmarking competition.Source: §2.2 · p. 3
  • Seismic displaced earlier graph-based approaches with an inverted index tailored to learned sparse embeddings and remains the paper’s primary baseline.Other specialized inverted-index systems include BMP, DSP, and SINDI.Source: §2.2 · p. 3

3 Methodology

GRIP combines term-seeded entry points, sparse-sketch routing, and sparse partition-based graph construction. These techniques bring inverted-index ideas into graph search while addressing search and construction costs for learned sparse retrieval.

3 Methodology

  • The methodology separates offline term-seed and graph construction from online beam search initialized with up to T·L nodes and routed on sketches.The final top-k documents are re-scored with full embeddings.Source: §3 · p. 3

3.1 Term-Seeded Entry Point Selection

  • GRIP initializes beam search with the union of seed lists for the T query terms with the largest q_t·w_t bounds, using each term’s L highest-weight documents.The precomputed lists contain each term’s L documents with the largest term weights; L=64, while T is selected by embedding type on held-out queries.Source: §3 · p. 3, §3.1 · p. 4

3.2 Approximate Routing via Sparse Sketching

  • Sparse sketches retain each document’s R largest-magnitude nonzero components for routing, then GRIP re-scores the final beam with full embeddings.For SPLADE-CoCondenser, R=80 retains 62% of average nonzero entries and speeds search 1.22–1.38× at recall@10 targets of 95%–99%.Source: §3.2 · pp. 4–5

3.3 Sparse PiPNN

  • Sparse graph search quality improves as construction efc rises from 200 to 2000, but building an HNSW graph at efc=2000 takes 5.5–7.4 hours on MS MARCO v1 and is estimated to take days on MS MARCO v2.The paper motivates sparse partition-based construction as an alternative to this costly search-based insertion approach.Source: §3.3 · p. 5, Figure 2 · p. 5
  • Sparse PiPNN replaces dense computations in partitioning and within-leaf similarity calculations with inverted-index computations, then adds a refinement pass on the finished graph.The refinement pass is described as important for search quality at very high recall targets.Source: §3.3 · p. 5
  • 47 minutes versus 5.5 hours: Sparse PiPNN builds the MS MARCO v1 graph faster than HNSW at efc=2000, while GRIP outperforms both Sparse PiPNN and HNSW.The comparison is for an 8.8M-passage collection.Source: §3.3 · p. 6

4 Experiments

GRIP improves graph-based sparse retrieval performance over Seismic on MS MARCO v1 and v2, while index construction and storage remain trade-offs. Experiments also compare its search optimizations and benchmark it against HNSW.

4 Experiments

  • On MS MARCO v1, GRIP runs 2.8–3.2× faster than HNSW with SPLADE-CoCondenser and 2.0–2.1× faster with SPARSEUP at 95%–98% recall@10.The gap narrows to 1.5× at 99% recall@10 with SPARSEUP.Source: §4 · p. 6
  • On MS MARCO v2, GRIP is 2.2–3.4× faster than Seismic at recall@10 targets from 90% to 98%.On MS MARCO v1, GRIP is 1.4–1.7× faster than Seismic for SPLADE-CoCondenser across 90%–99% recall@10; with SPARSEUP, it is faster at 92%–95%, roughly on par at 97%, and slower at 98% and above.Source: §4 · p. 6
  • Seismic has an order-of-magnitude faster build time than GRIP, while GRIP’s Sparse PiPNN construction reduces build time relative to HNSW with high efc.GRIP’s construction takes 7.3 hours at the 138M-passage scale, which the authors describe as practical for daily index rebuilding.Source: Table 1 · p. 6, §4 · p. 7
  • On MS MARCO v1, GRIP uses more space than Seismic with CoCondenser embeddings but less with SPARSEUP; on MS MARCO v2 with CoCondenser, it uses almost twice the space.The authors attribute the v2 difference primarily to GRIP storing an additional sketched copy of each vector.Source: §4 · p. 7, Table 2 · p. 7
  • Term-based seeding provides larger search gains than approximate routing, but the two optimizations are complementary and combine for a larger speedup than either alone.The ablation compares speedups over standard beam search on the same Sparse PiPNN graph at matched recall@10.Source: §4 · p. 7

5 Conclusion

GRIP combines inverted-index ideas with graph search to challenge the view that graph-based indexes are uncompetitive for learned sparse retrieval. The reported gains come with larger indexes and longer build times.

5 Conclusion

  • GRIP combines three optimizations—inverted-index-inspired term-based entry point seeding, approximate routing via sparse sketching, and Sparse PiPNN—to outperform Seismic by 2.2–3.4× on MS MARCO v2.The result is reported for the 138M-passage collection with SPLADE-CoCondenser embeddings.Source: §5 · p. 7
  • The search ablation finds that term-based seeding supplies most of the efficiency gains, while seeding and routing together outperform either alone.The comparison uses matched recall@10 on the same Sparse PiPNN graph.Source: Table 3 · p. 7
  • GRIP’s gains come with a larger index and longer build time than Seismic, leaving graph and vector compression as future work.The authors also identify exploring whether the combined-index insights generalize to other problems as future work.Source: §5 · p. 7

Related papers

Loading 2610.30425v1…