AI Paper Atlas

Research map / Learning theory and algorithms / Prediction and decision losses

A Bi-metric Framework for Efficient Nearest Neighbor Search

Haike Xu, Sandeep Silwal, Piotr Indyk

ICML 2026 · Learning theory and algorithms › Prediction and decision losses · approach: Approximate nearest neighbor indexing

Read the paperCheck your idea against 137,217 papers

AI-extracted. The measured effects below were read by AI from the paper's full text (no summary yet). Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Measured effects reported in the paper

What was changedWhereMeasuredEffect
run graph search with expensive metric D on a graph index built with cheap metric d, seeded from the cheap-metric top-Q/2 results, instead of retrieve-then-rerankDiskANN bi-metric search · HotpotQA, bge-micro-v2 + SFR-Embedding-Mistralcalls to D for matched NDCG@10: 8000 -> <2000 callsImproved
bi-metric search with Gemini-2.0-Flash as the expensive comparatorDiskANN bi-metric search · 6 large BEIR datasets (avg)Gemini API calls at equal accuracy: ≈800 -> ≈200 callsImproved
build index with cheap metric d instead of expensive metric D (single metric)DiskANN bi-metric search · 6 BEIR datasets, NDCG@10convergence speedImproved
use a cheap proxy model with a larger quality gap to the expensive model (ablation)bi-metric search · HotpotQA (bge-micro, gte-small, bge-base)NDCG@10 gain over re-rankingImproved
start second-stage search from top-100 or top-Q/2 first-stage results instead of top-1 or the default entry point (ablation)bi-metric second-stage search · HotpotQANDCG@10Improved
start second-stage search from only the top-1 first-stage point (ablation)bi-metric second-stage search · HotpotQANDCG@10Hurt
swap DiskANN for NSG as graph index (ablation)bi-metric search · BEIR retrievalNDCG@10No clear effect
apply bi-metric framework to LSH-style partition methodsLSH · theory (adversarial dataset)query timeHurt

Closest papers by meaning

Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.

Open scime draft

Get the next scime Dispatch and a monthly field update

Free. We send a confirmation link first; every email has a one-click unsubscribe. Privacy