A Bi-metric Framework for Fast Similarity Search

Nearest-neighbor indexes usually rely on a single distance function, but accurate comparisons can be expensive. This talk proposes a bi-metric framework: a cheap proxy metric builds the index, while the query procedure uses a limited number of evaluations of both the proxy and an expensive ground-truth metric. The theory applies to DiskANN and Cover Tree. When the proxy approximates the ground-truth metric within a bounded factor, the resulting structure can achieve arbitrarily good approximation guarantees under the accurate metric. Experiments on text retrieval using models with very different computational costs show improved accuracy-efficiency tradeoffs on almost all MTEB datasets compared with alternatives such as reranking. Joint work with Haike Xu and Sandeep Silwal.