All posts

Graph or Inverted Index? Learned Sparse Retrieval at the SISAP 2026 Indexing Challenge

by tusKANNy team
Learned Sparse RetrievalChallengeSeismickANNolo

At the SISAP 2026 Indexing Challenge1 we entered Task 3, approximate search over learned sparse embeddings, with two different indexes: a graph built with kANNolo and an inverted index built with Seismic. They finished first and second on the leaderboard.

The task

The collection is the 2.68 million passages of the Natural Questions2 collection from BEIR3, encoded with SPLADE-v34: vectors over the 30,522 terms of the BERT vocabulary, with about 214 nonzero entries per document and 27 per query. For each query we had to return the 30 documents with the highest dot product, finding at least 90% of the true ones (Recall@30 ≥ 0.90), as fast as possible. Systems ran on 8 vCPUs (AVX2 only) with 24 GB of RAM, and had 8 hours to build the index and run up to 15 search configurations. Only search time was scored.

Learned sparse retrieval has no settled answer on which index to use. The sparse track of the NeurIPS 2023 Big ANN challenge5 was won by adaptations of HNSW6, but since then dedicated inverted indexes such as Seismic7, BMP8, DSP9 and SINDI10 have taken the lead. We entered one of each. Both are written in Rust on top of Vectorium, our library for storing and scoring vectors, so they share the same float16 storage, the same dot-product kernels and the same optimizations. The two entries differ only in how they organize vectors and collect candidates.

kANNolo: a graph over pruned vectors

The kANNolo11 entry is the two-stage index described in our previous post, built on RerankIndex12. Each document keeps only its heaviest entries, those carrying 75% of its L1 mass (41% of its nonzeros on NQ), and the HNSW graph is built over these pruned vectors. At query time the graph returns a few dozen candidates, which are rescored exactly with the full vectors. This works because a learned sparse vector concentrates most of its inner product in a few large entries7. We picked 75% with a small exhaustive study on FIQA: at 70%, the top 100 of the pruned collection already contains more than 99% of the true top 30.

Compared with HNSW over the full vectors and with the same build parameters, the two-stage index is 1.4× faster at 90% recall and almost 2× faster at 94.5%, and its graph builds 37% faster (2.3 against 3.75 hours).

Seismic: an inverted index with a graph on top

Seismic keeps, for each term, only the documents with the largest weights for it, and splits each of these posting lists into blocks of semantically-related documents using clustering. Every block stores a summary, an upper bound on the score of any document inside it, so a query can skip whole blocks without opening them. Only the 4 or 5 heaviest terms of the query are traversed.

Our entry uses the Seismic-Wave variant13, which adds a refinement step using a κ-NN graph over the documents. After the traversal, the best candidates are expanded with their nearest neighbors, and all of them are rescored with the full query. Neighbors of good candidates tend to be good candidates too, so this short refinement step gains a lot of recall, where the inverted index alone would need a longer exploration to get the same gain. In our best configuration on the development set reaching Recall@30 ≥ 0.90, expanding each candidate with 10 neighbors raised recall from 84.6% to 90.1% for about 70 µs more per query on a single thread.

Results

Final results of SISAP 2026 Task 3 on the test queries with 8 threads: tusKANNy-seismic 15,870 queries per second, tusKANNy-kANNolo 9,320, hanswurst 958, basque-invaders 404, luis 204.

On the hidden test queries, with 8 threads, Seismic answered 15,870 queries per second and kANNolo 9,320, against 958 for the next entry.

Single-thread query latency on the development queries. Left: plain HNSW against kANNolo's two-stage index, 867 against 611 µs at 0.90 recall up to 1,851 against 947 µs at 0.945. Right: kANNolo against Seismic, 611 against 498 µs at 0.90, 826 against 651 at 0.93, 1,034 against 940 at 0.95.

On the development queries with a single thread, Seismic reaches 90% recall in 498 µs against 611 µs for kANNolo, about 20% faster, and the gap shrinks at higher recall: 940 against 1,034 µs at 95%. On the test queries with 8 threads it was larger, about 70%. Seismic also builds much faster (11 minutes against 2.5 hours), while kANNolo's index is smaller (2.6 against 4.9 GiB). The code of both entries is on GitHub: kANNolo and Seismic.

Graph or inverted index?

Thanks to the work of the information retrieval community over the last four years, inverted indexes now dominate learned sparse retrieval. Graph indexes still use less memory, and we believe they have room to improve. Either way, a single dataset is not enough to settle the question. We have been running a much larger comparison of kANNolo, Seismic and the state-of-the-art learned sparse retrieval systems, and the results are coming soon. Stay tuned.

References

  1. Martin Aumüller, Maik Fröbe, Vladimir Mic, Eric S. Tellez. Overview of the SISAP 2026 Indexing Challenge: k-NN Graphs, LLM Workloads, and Sparse Embeddings. SISAP, 2026. ↩

  2. Tom Kwiatkowski, Jennimaria Palomaki, Olivia Redfield, et al. Natural Questions: A Benchmark for Question Answering Research. Transactions of the Association for Computational Linguistics, 2019. doi:10.1162/tacl_a_00276 ↩

  3. Nandan Thakur, Nils Reimers, Andreas Rücklé, Abhishek Srivastava, Iryna Gurevych. BEIR: A Heterogeneous Benchmark for Zero-shot Evaluation of Information Retrieval Models. NeurIPS Datasets and Benchmarks Track, 2021. openreview.net ↩

  4. Carlos Lassance, Hervé Déjean, Thibault Formal, Stéphane Clinchant. SPLADE-v3: New baselines for SPLADE. arXiv, 2024. arXiv:2403.06789 ↩

  5. Harsha Vardhan Simhadri, Martin Aumüller, Amir Ingber, Matthijs Douze, et al. Results of the Big ANN: NeurIPS'23 Competition. arXiv, 2024. arXiv:2409.17424 ↩

  6. Yu A. Malkov, D. A. Yashunin. Efficient and Robust Approximate Nearest Neighbor Search Using Hierarchical Navigable Small World Graphs. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2020. doi:10.1109/TPAMI.2018.2889473 ↩

  7. Sebastian Bruch, Franco Maria Nardini, Cosimo Rulli, Rossano Venturini. Efficient Inverted Indexes for Approximate Retrieval over Learned Sparse Representations. SIGIR, 2024. semanticscholar.org ↩ ↩2

  8. Antonio Mallia, Torsten Suel, Nicola Tonellotto. Faster Learned Sparse Retrieval with Block-Max Pruning. SIGIR, 2024. ↩

  9. Parker Carlson, Wentai Xie, Shanxiu He, Tao Yang. Dynamic Superblock Pruning for Fast Learned Sparse Retrieval. SIGIR, 2025. ↩

  10. Ruoxuan Li, Xiaoyao Zhong, Jiabao Jin, et al. SINDI: An Efficient Index for Approximate Maximum Inner Product Search on Sparse Vectors. arXiv, 2025. ↩

  11. Leonardo Delfino, Domenico Erriquez, Silvio Martinico, Franco Maria Nardini, Cosimo Rulli, Rossano Venturini. kANNolo: Sweet and Smooth Approximate k-Nearest Neighbors Search. ECIR, 2025. doi:10.1007/978-3-031-88717-8_29 ↩

  12. Silvio Martinico, Franco Maria Nardini, Cosimo Rulli, Rossano Venturini. Multivector Reranking in the Era of Strong First-Stage Retrievers. ECIR, 2026. doi:10.1007/978-3-032-21324-2_4 ↩

  13. Sebastian Bruch, Franco Maria Nardini, Cosimo Rulli, Rossano Venturini. Pairing Clustered Inverted Indexes with κ-NN Graphs for Fast Approximate Retrieval over Learned Sparse Representations. CIKM, 2024. doi:10.1145/3627673.3679977 ↩