# Bridging Dense and Sparse Maximum Inner Product Search

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

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 16 Sep 2023.

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

- [Balancing the Blend: An Experimental Analysis of Trade-offs in Hybrid Search](https://mlsanity.com/paper/2508.01405/) (2025)
- [Optimistic Query Routing in Clustering-based Approximate Maximum Inner Product Search](https://mlsanity.com/paper/2405.12207/) (2024)
- [To Copy, or not to Copy; That is a Critical Issue of the Output Softmax Layer in Neural Sequential Recommenders](https://mlsanity.com/paper/2310.14079/) (2023)
- [Efficient Sketching and Nearest Neighbor Search Algorithms for Sparse Vector Sets](https://mlsanity.com/paper/2509.24815/) (2025)
- [Exact Adaptive Hybrid Retrieval Without Fixed Top-L Cutoffs](https://mlsanity.com/paper/2608.07152/) (2026)
- [All-in-one Graph-based Indexing for Hybrid Search on GPUs](https://mlsanity.com/paper/2511.00855/) (2025)
- [Neighborhood Stability as a Measure of Nearest Neighbor Searchability](https://mlsanity.com/paper/2602.16673/) (2026)
- [Finder: A Multimodal AI-Powered Search Framework for Pharmaceutical Data Retrieval](https://mlsanity.com/paper/2603.15623/) (2026)

## Abstract (arXiv)

Maximum inner product search (MIPS) over dense and sparse vectors have progressed independently in a bifurcated literature for decades; the latter is better known as top-k retrieval in Information Retrieval. This duality exists because sparse and dense vectors serve different end goals. That is despite the fact that they are manifestations of the same mathematical problem. In this work, we ask if algorithms for dense vectors could be applied effectively to sparse vectors, particularly those that violate the assumptions underlying top-k retrieval methods. We study IVF-based retrieval where vectors are partitioned into clusters and only a fraction of clusters are searched during retrieval. We conduct a comprehensive analysis of dimensionality reduction for sparse vectors, and examine standard and spherical KMeans for partitioning. Our experiments demonstrate that IVF serves as an efficient solution for sparse MIPS. As byproducts, we identify two research opportunities and demonstrate their potential. First, we cast the IVF paradigm as a dynamic pruning technique and turn that insight into a novel organization of the inverted index for approximate MIPS for general sparse vectors. Second, we offer a unified regime for MIPS over vectors that have dense and sparse subspaces, and show its robustness to query distributions.