# Efficient Sketching and Nearest Neighbor Search Algorithms for Sparse Vector Sets

arXiv: https://arxiv.org/abs/2509.24815 · HTML: https://mlsanity.com/paper/2509.24815/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 38 of its 73 references that are in the map.
- First posted on arXiv 29 Sep 2025.

## Builds on (most cited first, 30 of 38)

- [BERT: Pre-training of Deep Bidirectional Transformers for Language Understanding](https://mlsanity.com/paper/1810.04805/) (2018)
- [Billion-scale similarity search with GPUs](https://mlsanity.com/paper/1702.08734/) (2017)
- [MS MARCO: A Human Generated MAchine Reading COmprehension Dataset](https://mlsanity.com/paper/1611.09268/) (2016)
- [Google's Neural Machine Translation System: Bridging the Gap between Human and Machine Translation](https://mlsanity.com/paper/1609.08144/) (2016)
- [Sparse Autoencoders Find Highly Interpretable Features in Language Models](https://mlsanity.com/paper/2309.08600/) (2023)
- [BEIR: A Heterogenous Benchmark for Zero-shot Evaluation of Information Retrieval Models](https://mlsanity.com/paper/2104.08663/) (2021)
- [Efficient and robust approximate nearest neighbor search using Hierarchical Navigable Small World graphs](https://mlsanity.com/paper/1603.09320/) (2016)
- [Sparse Feature Circuits: Discovering and Editing Interpretable Causal Graphs in Language Models](https://mlsanity.com/paper/2403.19647/) (2024)
- [Gemma Scope: Open Sparse Autoencoders Everywhere All At Once on Gemma 2](https://mlsanity.com/paper/2408.05147/) (2024)
- [Sketching as a Tool for Numerical Linear Algebra](https://mlsanity.com/paper/1411.4357/) (2014)
- [SPLADE: Sparse Lexical and Expansion Model for First Stage Ranking](https://mlsanity.com/paper/2107.05720/) (2021)
- [Pretrained Transformers for Text Ranking: BERT and Beyond](https://mlsanity.com/paper/2010.06467/) (2020)
- [Llama Scope: Extracting Millions of Features from Llama-3.1-8B with Sparse Autoencoders](https://mlsanity.com/paper/2410.20526/) (2024)
- [SPLADE v2: Sparse Lexical and Expansion Model for Information Retrieval](https://mlsanity.com/paper/2109.10086/) (2021)
- [From Distillation to Hard Negative Sampling: Making Sparse Neural IR Models More Effective](https://mlsanity.com/paper/2205.04733/) (2022)
- [SPLADE-v3: New baselines for SPLADE](https://mlsanity.com/paper/2403.06789/) (2024)
- [A Few Brief Notes on DeepImpact, COIL, and a Conceptual Framework for Information Retrieval Techniques](https://mlsanity.com/paper/2106.14807/) (2021)
- [Identifying Functionally Important Features with End-to-End Sparse Dictionary Learning](https://mlsanity.com/paper/2405.12241/) (2024)
- [Context-Aware Sentence/Passage Term Importance Estimation For First Stage Retrieval](https://mlsanity.com/paper/1910.10687/) (2019)
- [SPARTA: Efficient Open-Domain Question Answering via Sparse Transformer Matching Retrieval](https://mlsanity.com/paper/2009.13013/) (2020)
- [SparTerm: Learning Term-based Sparse Representation for Fast Text Retrieval](https://mlsanity.com/paper/2010.00768/) (2020)
- [Expansion via Prediction of Importance with Contextualization](https://mlsanity.com/paper/2004.14245/) (2020)
- [An Efficiency Study for SPLADE Models](https://mlsanity.com/paper/2207.03834/) (2022)
- [Efficient Inverted Indexes for Approximate Retrieval over Learned Sparse Representations](https://mlsanity.com/paper/2404.18812/) (2024)
- [Adaptive Re-Ranking with a Corpus Graph](https://mlsanity.com/paper/2208.08942/) (2022)
- [Results of the Big ANN: NeurIPS'23 competition](https://mlsanity.com/paper/2409.17424/) (2024)
- [Wacky Weights in Learned Sparse Representations and the Revenge of Score-at-a-Time Query Evaluation](https://mlsanity.com/paper/2110.11540/) (2021)
- [Sparse Autoencoders Enable Scalable and Reliable Circuit Identification in Language Models](https://mlsanity.com/paper/2405.12522/) (2024)
- [A Static Pruning Study on Sparse Neural Retrievers](https://mlsanity.com/paper/2304.12702/) (2023)
- [Faster Learned Sparse Retrieval with Block-Max Pruning](https://mlsanity.com/paper/2405.01117/) (2024)

## Built on by (most cited first, 1 of 1)

- [LACONIC: Dense-Level Effectiveness for Scalable Sparse Retrieval via a Two-Phase Training Curriculum](https://mlsanity.com/paper/2601.01684/) (2026)

## Abstract (arXiv)

Sparse embeddings of data form an attractive class due to their inherent interpretability: Every dimension is tied to a term in some vocabulary, making it easy to visually decipher the latent space. Sparsity, however, poses unique challenges for Approximate Nearest Neighbor Search (ANNS) which finds, from a collection of vectors, the k vectors closest to a query. To encourage research on this underexplored topic, sparse ANNS featured prominently in a BigANN Challenge at NeurIPS 2023, where approximate algorithms were evaluated on large benchmark datasets by throughput and accuracy. In this work, we introduce a set of novel data structures and algorithmic methods, a combination of which leads to an elegant, effective, and highly efficient solution to sparse ANNS. Our contributions range from a theoretically-grounded sketching algorithm for sparse vectors to reduce their effective dimensionality while preserving inner product-induced ranks; a geometric organization of the inverted index; and the blending of local and global information to improve the efficiency and efficacy of ANNS. Empirically, our final algorithm, dubbed Seismic, reaches sub-millisecond per-query latency with high accuracy on a large-scale benchmark dataset using a single CPU.