A Bi-metric Framework for Efficient Nearest Neighbor Search

We propose a new ``bi-metric'' framework for designing nearest neighbor data structures. Our framework assumes two dissimilarity functions: a ground-truth metric that is accurate but expensive to compute, and a proxy metric that is cheaper but less accurate. In both theory and practice, we show how to construct data structures using only the proxy metric such that the query procedure achieves the accuracy of the expensive metric, while only using a limited number of calls to both metrics. Our theoretical results instantiate this framework for two popular nearest neighbor search algorithms: DiskANN and Cover Tree. In both cases we show that, as long as the proxy metric used to construct the data structure approximates the ground-truth metric up to a bounded factor, our data structure achieves arbitrarily good approximation guarantees with respect to the ground-truth metric. On the empirical side, we apply the framework to the text retrieval problem with two dissimilarity functions evaluated by ML models with vastly different computational costs. We observe that for almost all the large data sets in the BEIR benchmark, our approach achieves a considerably better accuracy-efficiency tradeoff than the alternatives, such as retrieve-then-rerank.

This paper studies how to make large-scale retrieval systems both accurate and efficient. In many applications, the best similarity model is expensive to run, while a cheaper model is faster but less accurate. We propose a bi-metric framework that builds the search index using only the cheap proxy metric, but uses the expensive metric during query-time search to guide the algorithm toward better results. We prove that this idea works for graph-based nearest neighbor methods such as DiskANN and Cover Tree, giving accuracy guarantees with respect to the expensive metric. Experiments on large BEIR text retrieval datasets show that our method achieves better accuracy-efficiency tradeoffs than standard retrieve-then-rerank baselines, often reaching similar accuracy with far fewer expensive model calls.