Research map / Architectures and efficiency / RNNs and normalization

LotusFilter: Fast Diverse Nearest Neighbor Search via a Learned Cutoff Table

CVPR 2025 · Architectures and efficiency › RNNs and normalization · approach: Learned embeddings for retrieval · 1 citations (OpenAlex)

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Proposes LotusFilter, a post-processing module that uses a precomputed cutoff table of close-neighbor IDs, with an ε threshold learned from training queries, to greedily diversify HNSW nearest-neighbor search results at about 0.02 ms/query filtering cost.

Problem

Approximate nearest neighbor search returns results that are close to the query but highly similar to each other, while many applications (e.g., RAG, recommendation, image retrieval) need results that are both similar to the query and diverse; existing diverse NN search methods are slow and need ori

Approach

Precompute, for each database vector, the list of neighbors within a squared-distance threshold ε (a cutoff table); at query time, greedily pop the nearest remaining candidate and delete its listed neighbors from the candidate set, using an OrderedSet for O(L) pop/remove. The threshold ε is learned by bracketing search over training queries, and the method needs no original vectors at query time.

Key results

• On the OpenAI dataset (K=100, S=500), LotusFilter reaches the best cost f=0.171 versus 0.200 for search-only, 0.223 for clustering, and 0.177 for GMM, at 1.03 ms/query total (filter 0.02 ms/query).
• Clustering and GMM use about 40 times more memory than LotusFilter (4.42e10 bits vs 1.14e9 bits for 9e5 vectors).
• Training epsilon by bracketing on training queries gives a reasonable but imperfect solution; the training step takes about 1,100 s and cutoff-table construction about 1 minute for N=9e5.

Measured effects reported in the paper

Surprising findings

• Clustering performs worst among the diversification methods on final cost, despite being simple and widely used.
• For low-dimensional vectors, simpler baselines such as GMM may be more effective than LotusFilter.

Limitations

• Requires preprocessing (cutoff table construction and epsilon tuning) and extra memory of 64LN bits.
• Epsilon is learned for a fixed K, and a single global threshold may not suit all datasets.
• Only the diversity-proximity cost is evaluated; no end-to-end RAG evaluation or LLM-as-a-judge assessment.

Experimental setup

Datasets: OpenAI embedding dataset (WikiText, 1536-d, 900k base / 100k queries) MS MARCO v1.1 validation passages (768-d BERT features, 38,438 base / 1,000 queries) Revisited Paris (2048-d R-GeM, 6,322 base / 70 queries)

Benchmarks: OpenAI embedding dataset MS MARCO Revisited Paris

Metrics: cost function f (proximity plus diversity) runtime ms/query memory overhead bits Recall@1

Baselines: HNSW search only k-means clustering diversification GMM diversification

Builds on: HNSW faiss MAX-MIN diversification GMM diversification maximal marginal relevance

Closest papers by meaning

• Graph-Based Algorithms for Diverse Similarity Search (ICML 2025 · similarity 0.87)
• Approximate Nearest Neighbor Search with Window Filters (ICML 2024 · similarity 0.85)
• Results of the Big ANN: NeurIPS’23 competition (NeurIPS 2025 · similarity 0.84)
• LoRANN: Low-Rank Matrix Factorization for Approximate Nearest Neighbor Search (NeurIPS 2024 · similarity 0.84)
• CSPG: Crossing Sparse Proximity Graphs for Approximate Nearest Neighbor Search (NeurIPS 2024 · similarity 0.84)
• Ensemble Learned Bloom Filters: Two Oracles are Better than One (ICML 2025 · similarity 0.83)