acceptodds
Under review as a conference paper at ICLR 2027

Infinity Search: Approximate Vector Search with Projections on q-Metric Spaces

Abstract

An ultrametric space or infinity-metric space is defined by a dissimilarity function that satisfies a strong triangle inequality in which every side of a triangle is not larger than the larger of the other two. We show that search in ultrametric spaces with a vantage point tree has worst-case complexity equal to the depth of the tree. Since datasets of interest are not ultrametric in general, we employ a projection operator that transforms an arbitrary dissimilarity function into an ultrametric space while preserving nearest neighbors. We further learn an approximation of this projection operator to efficiently compute ultrametric distances between query points and points in the dataset. We proceed to solve a more general problem in which we consider projections in q-metric spaces – in which triangle sides raised to the power of q are smaller than the sum of the q-powers of the other two. Notice that the use of learned approximations of projected q-metric distances renders the search pipeline approximate. We show in experiments that increasing values of q result in faster search but lower recall. Overall, search in q-metric and infinity metric spaces is competitive with existing search methods.

Primary area:
other topics in machine learning (i.e., none of the above)
Keywords:
Nearest-neighbor search, similarity search, metric trees (VP-trees), triangle inequality, generalized metrics, high-dimensional data, logarithmic complexity, vector search, text retrieval, image retrieval, dissimilarity measures.

Reviews

Among:
Shape:
1234this paper, Top 49%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.33 over 3 reviews, above 51% of the others.
Reviewer_1A23OpenReview ↗
Rating
1
Confidence
3
Informativeness
1
Presentation
2
Soundness
2
Read review
Paper summary

The paper proposes to accelerate nearest-neighbour (NN) search by changing the metric of the data before the search. The proposition is to map the original dissimilarity on the data to a canonical qq-metric projection of Segarra et al. By doing so the authors obtain a new distance where the length of a path is the ℓq\ell_q norm of its edge weights. A VP-tree is then built in the projected space and searched with pruning rules adapted to the qq-triangle inequality.

Critical strengths
  • Changing the metric structure of the data so that tree pruning and thus, NN-search becomes easier is an interesting direction.
  • Build time and memory are reported along with queriers per second. The appendix includes additional experiments that openly show the behavior of the method over several dissimilarities and at large qq.
Critical weaknesses

Theory

Theorem 1 does not apply to the proposed method

Theorem 1 is correct as stated: if one ultrametric distance dd on X∪{xo}X\cup\{x_o\} is used both to build and to search the tree, the search finds a nearest neighbour. The problem is that the proposed method, does not have in general has such an ultrametric distance. The proof of this theorem, which goes through Proposition 4, relies on the strong triangular inequality. For a triangle (v,xo,x)(v, x_o, x), the side d(v,x)d(v,x) comes from the tree, through the radius μ\mu. The other two sides, d(v,xo)d(v,x_o) and d(xo,x)d(x_o,x), are the query distances used during the search. In the methods of Sections 2.4 and 3.1, these two distances come from two different projections:

  • the tree distance is built by setting D∞=P∞⋆(X)D_\infty=P^\star_\infty(X)
  • the query is compared through E∞E_\infty, the projection of the graph that also contains xox_o (Section 3.1, Prop. 1).

Adding xox_o to the graph adds all paths that go through the query: for x,y∈Xx,y\in X

E∞(x,y)=min⁡(D∞(x,y), max⁡(E∞(x,xo), E∞(xo,y))).E_\infty(x,y)=\min\Big(D_\infty(x,y),\ \max\big(E_\infty(x,x_o),\,E_\infty(x_o,y)\big)\Big).

The two projections therefore disagree when the query lies between two groups of points. For such a pair, D∞(v,x)>max⁡(E∞(v,xo),E∞(xo,x))D_\infty(v,x)>\max\big(E_\infty(v,x_o),E_\infty(x_o,x)\big). The inequality used in the proof then fails, and the rule (∞-CI) can discard the branch that contains the NN.

Proof of Theorem 2 is incomplete

The appendix proof (App. E.1) which is called "Existence and uniqueness" proves only existence. Equation (45) requires that d(x,x′)d(x,x') satisfies the qq-triangle inequality which doesn't appears obvious to me.

The axiomatic justification is weak.

Axioms (A1)–(A2) implies that only one map satisfies them. They are not related strongly to what matters for search: recall, tree balance, number of ties, etc. Those axioms also ruled out other ultrametric fits without being tested at least experimentally to compare the performances.

Minor

The second inequality in (63) is false in general: it compares a path to x1x_1 with the shortest path to zz. The statement itself is true, since any path from xox_o has a first edge ≥min⁡xE(xo,x)\ge \min_x E(x_o,x) and, for q<∞q<\infty, any additional edge makes it strictly longer.

Novelty with respect to prior work

The canonical ∞\infty-projection given in Algorithm 5 is the minimax path distance, i.e. the subdominant ultrametric or the single-linkage cophenetic distance. It can be computed in O(n2)O(n^2) through a minimum spanning tree (Gower & Ross, 1969), compared with O(n3)O(n^3) for the Floyd–Warshall approach of Algorithm 5. Neither other recent methods of the litterature on ultrametric fitting (Cohen-Addad et al, 2020) or space partitioning for NN-search are compared (e.g.(Dasgupta et al, 2013) or (Dong et al, 2020)).

Algorithms

  • For vantage points, Algorithm 1 picks a vantage point at random. The Remark 2 below acknwoledge the fact that the the choice "may have a significant effect in practive" and mentions an heuristic to choose it. The paper never says which rule the experiments use, and there is no ablation.
  • Algorithm 1 takes the median over all x∈Xx\in X, which includes d(v,v)=0d(v,v)=0, unlike eq. (10). Also, X′′={x:d(x,v)≥μ}X''=\{x: d(x,v)\ge\mu\} does not exclude vv. For X={v}X=\{v\} this gives μ=0\mu=0 and X′′={v}X''=\{v\}, so the recursion never terminates.

Presentation

The paper is very hard to read.

  • Assertions in place of arguments: "(very justifiable) Axioms" (l.68); "the data is what the data is" (l.59–60) etc. Those should be detailed or deleted if bringing nothing to the paper.
  • Numbering and cross-references. I give here only a sample of examples. "Theorem 1" appears twice in the appendix with different content. Proposition 5 repeats Proposition 1. Proposition 12 (l.1726) reference to Proposition 1. Proposition 4 refers to "(4)" for the strong triangle inequality, which is eq. (3), and its proof uses "(∞-CI)" where (∞-CO) is meant (l.904).
  • Typos: "bearest", "neioghbor", "tims", "lmited", "REULTS", "ouperformed" etc.
  • The conclusion and the related work are both in the appendix.
Questions for authors
  1. In the exact-projection experiments is the tree built on Pq⋆(X)P^\star_q(X) and searched with Eq(xo,⋅)E_q(x_o,\cdot)? Or is it rebuilt for each query on Pq⋆(X∪{xo})P^\star_q(X\cup\{x_o\})?
  2. How are vantage points chosen in the reported experiments: at random, as in Algorithm 1, or with a spread heuristic? How sensitive are the quality metrics to this choice?
  3. What are the end-to-end build times, including the projection on the training subset, the kNN graph and MLP training? What is the QPS when the query embedding is included?
  4. Why does ℓD\ell_D increase during training in Fig. 23? What happens if Φ\Phi is trained with the contrastive loss only?
  5. How large is arg⁡min⁡xE∞(xo,x)\arg\min_x E_\infty(x_o,x) on the real datasets that you choose?
5 comments

We thank the reviewer for his time, effort and valuable comments.

Theorem 1 Does Not Apply to the Proposed Method

The reviewer is correct that Theorem 1 considers cases in which ultrametric distances are available. In most practical situations, this is not the case and we propose the use of a learning parametrization to estimate ultrametric distances (or q-metric distances in general).

Concluding from these facts that “Theorem 1 does not apply to the proposed method” is, however, an overstatement. Theorem 1 motivates our approach. This is analogous to, for example, the relationship between HNSW and Small World Graphs (SWGs). In general, data does not follow an exact Small World Graph, however an approximate SWG constructed by HNSW is efficient for search. I.e., SWGs motivate HNSW in more or less the same way in which Theorem 1 motivates our proposed approach.

The Axioms Do Not Relate to Search

Axiom 1 establishes that the q-metric structure is preserved by the projection. This implies that if the data is already efficiently searchable, we do not alter the structure of the data.

Axiom 2 does not increase distances. This implies the preservation of nearest neighbor information, thus the preservation of recall.

To the extent that preserving efficiency and recall matter for nearest-neighbor search, the axioms are well justified. Other axioms may be imposed, but the uniqueness result dictates that other properties will be either implied by Axioms 1 and 2 or result in the nonexistence of a projection operator. We will clarify these connections in the revised manuscript.

Novelty

We are not sure what the reviewer means by “novelty with respect to prior work.” Our novelty is proposing the use of q-metric projections for search. We do not claim that the method for constructing q-metric projections is novel. In particular, the reviewer is right that MST is a more efficient method for constructing the ultrametric (but not q-metrics), but this is not the point of the manuscript.

The other three contributions mentioned by the reviewer do not overlap with our paper. Cohen-Addad et al. (2020) does not use our ultrametric space and Dasgupta and Sinha (2013) and Dong et al. (2020) do not propose an ultrametric. We do not see much overlap with either of these papers. We will clarify this in the revised version of the paper.

We do not understand which comparisons you would like us to add relative to these contributions. Our paper already includes comparisons with state of the art search methods.

Algorithm 1 is Wrong

Algorithm 1 is correct as stated: Line 3 reads, “choose a vantage point” from X, which is in general agreed to mean that we remove the vantage point from X.

We will nevertheless update Line 4 in the revised paper to write MEDIAN_X \ {v} instead of MEDIAN_X to make this convention more explicit.

Incomplete Proof of Theorem 2

The reviewer states that the proof of Theorem 2 establishes existence but not uniqueness. This is correct. We will add the proof of uniqueness to the revised manuscript.

Notice that this theorem and its proof are originally from Segarra el al (2019) and are included here for completeness. Thus, this is a simple problem to fix. We do accept that not including this proof was an oversight in preparing the manuscript. Please accept our apologies.

The Paper is Very Hard to Read

The reviewer points out some typos and opinions. Typos will be corrected and opinions will be removed.

Tree Construction and Tree Search

The reviewer asks if the tree is reconstructed for every query in the exact-projection investigations (Figure 14). The answer is yes. We do rebuild the tree for every query in these experiments.

Notice that these experiments are intended to showcase theoretical soundness. They are separate from our benchmark search results that construct the VP tree only once.

Selection of the vantage points

The reviewer asks for more detail on the selection of vantage points during construction of the VP tree.

During construction of the VP tree, we select the vantage point that maximizes the threshold μ\mu. This is motivated by the fact that accuracy of the tree depends on whether the generalization of the learned map Φ\Phi falls below the minimum threshold (Figure 4).

We compare the use of this technique to random choice of vantage points and maximum threshold variance σ(μ)\sigma(\mu) choice of vantage points:

Table 1. We construct the VPTree with different vantage point selection rules and report the Recall@1.

RuleSIFTDeep1BGISTKosarak
Random election0.9090.9060.9020.893
Maximum variance0.9110.9080.9130.893
Maximum threshold (ours)0.9170.9030.9210.900

We see that proper choice of vantage points has a small effect on recall.

Training and Index Building Times

The reviewer requests that we report times for computing q-metric projections, for training the estimator of q-metric distances and for building the VP tree. Times in seconds for the 4 large-scale examples are reported in the table below:

Table 2a. We report the building times of Projection, Training and Building phases in seconds.

SIFTDeep1BGISTKosarak
Projection33438734
Training43403650
Tree build810172
Total849314086

These costs are incurred only once per dataset. It is incorrect to assign their cost to individual queries. This is just a function of how many queries are conducted. In practice, preprocessing costs are amortized over a very large number of queries.

An important observation is that if we add points to the dataset, we recompute the VP tree but do not necessarily recompute the projection and learned estimator of q-metric distances. In fact, in all of the four datasets in the above table we compute the projection and train the distance estimator on a random subset of the entire dataset containing less than 10% of all points. We observe that this is enough to learn a distance estimator that generalizes well to the entire dataset (see Figure 4). These estimated distances are the ones used to build the VP tree.

Tension between Contrastive Loss and ℓD\ell_D

The reviewer is concerned about the increase of the loss ℓD\ell_D reported while training the approximate projection of the SIFT dataset.

We train the distance estimator with a loss that is the sum of two different terms. Each of these terms may increase during training as long as the total loss (their sum) decreases.

The reviewer also asks for an ablation experiment where the approximate projection is trained by using only the contrastive loss. Results are reported below:

Table 3. We train an approximate projection with only a contrastive loss ℓC\ell_C, and report the Recall@1 achieved by the index.

ModelSIFTDeep1BGISTKosarak
Original0.90.90.90.9
ℓC\ell_C0.40.60.30.7

Because the contrastive loss only accounts for relative neighbour ordering but does not encourage q-metric structure, it does not induce sufficient structure for effective search.

Minimum Projected Distance

The reviewer asks us to report the minimum distance produced by the canonical projection when q=∞q=\infty.

Proposition 1 states that this distance is the same as the minimum distance of the original dataset. I.e., that minimum distances are preserved under projection. This is a direct consequence of Axioms 1 and 2. The following table confirms this statement:

Table 4. We perform the canonical projection with q=∞q=\infty and report its minimum distance.

SIFTDeep1BGISTKosarak
Min E_\infty0.540.880.830.33
Min original d0.540.880.830.33

Theorem 1 My concern was specific: the tree is built from P∞⋆P^\star_\infty on XX, while the query is compared through P∞⋆P^\star_\infty on X∪{xo}X\cup\{x_o\}, where paths through xox_o can shorten distances. The strong triangle inequality used in Prop. 4 then fails across the two. Also it would be useful for the reader to state explicitely that the bound of Thm. 1 doesn't carry over the proposed experimental pipeline. It would also be good to report how often the pruning rule discards the branch containing the true nearest neighbor and how this fraction may vary with tree level.

Novelty My point was not that these papers propose the same ultrametric. Dasgupta and Sinha and Dong et al. are partition-based NN search methods, which solve the same problem as your VP-tree, and Cohen-Addad et al. fit ultrametrics in another way.

The Axioms Do Not Relate to Search First of all, I agree that other properties are implied or incompatible once uniqueness holds. You're reply states that Axiom 2 implies the preservation of the recall is a bit contradictory with what is noted in Appendix F.2 (line 1553). Please state those limitations directly in the main body. An experiment comparing the canonical projection with another ultrametric fit would also benefit the paper.

Incomplete Proof of Theorem 2 Thank you for adding the uniqueness proof. Please also fix the justification of (45) as I pointed out in my review.

Reviewer_N8GfOpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

The paper offers a way to accelerate nearest neighbor search in standard metric spaces by projecting them to ultrametric spaces, where NN search can be done faster.

The way to do it consists of two steps:

  1. First, perform a canonical q-metric projection based on all pairs q-norm shortest paths

2.Learn a network to map input vectors into an auxiliary space where Euclidean distances estimate q-metric shortest-path distances

Finally, do VP search followed by re-ranking to to find the nearest neighbors.

Results are competitive on some datasets.

Critical strengths

The idea seams elegant and novel. Map the data to a new space that is more amanable to VP-trees, whcih allows for faster retrieval.

Probably the most interesting part is the mathematical link between q-metric spaces and VP-tree branch pruning. Theorem 1 proves that searching in infinity-metric spaces has a worst-case comparison count bounded by the VP-tree depth. Specifically, the number of comparisons needed to find a nearest neighbor of a query in an ultrametric space is, at most, the depth of the VP tree.

The authors show empirically that ultrametric spaces are better suited to support VP-tree search and come up with a novel projection operator to map the data to that space.

Critical weaknesses
  1. The projection step might introduce spurios nearest neighbors

  2. The cost of the all-pairs (k-NN) shortest pathcan be large.

Questions for authors

Does the algorithm depend on the density of the points in the input dataset? Do you assume data is uniformly distributed?

1 comment

We thank the reviewer for the feedback.

The Projection Step Might Introduce Spurious NNs

This is correct. As the reviewer likely realizes, this is the motivation for reranking nearest neighbors after VP-tree search. We will explain this point better in the revised manuscript.

The Cost of all q-Shortest Path Projections Can be Large

This is correct. The cost of computing all q-shortest paths has complexity of order n2lognn^2logn for sparse graphs, which we use in practice (Algorithm 7).

This cost is incurred once per dataset.

Effect of Data Density on the Proposed Search Algorithm

The reviewer wonders about the effect of the data distribution in our results. This is a very good question.

The theoretical results in the paper do not depend on the data distribution but the performance in practice does. This is because the data distribution has an effect in the likelihood of adding spurious neighbors.

To illustrate this phenomenon we compare recall for data with a Gaussian distribution and data with a mixture of Gaussians distributions:

Table 1. We draw 20k points of dimension 30, from a mixture of k Gaussians and apply the canonical projection (q=∞q=\infty). Recall@1 is reported after searching with brute-force search.

Number of Gaussians k1505005005,000
Brute-force Recall@10.3680.3750.4620.4320.692

As the table illustrates, recall is better for the mixture of Gaussians. This happens because the ultrametric projection may add spurious neighbors within the same kernel of the Gaussian mixture but is unlikely to add spurious neighbours in a different kernel.

This synthetic experiment helps to explain why spurious neighbors are a manageable problem in practical datasets. Since different “concepts” tend to be represented by different directions in embedding space, practical datasets look more like a mixture of Gaussians than plain Gaussians.

Reviewer_1ZzAOpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

This paper proposes a technique for approximate nearest neighbor search via "qq-metric spaces". These qq-metric spaces are a generalization of standard metric spaces. For q≥1q \geq 1, a distance measure dd is said to be a qq-metric space if for any points x,y,zx,y,z, we have $ d(x,z)^q \leq d(x,y)^q + d(y,z)^q$. When q=1q = 1, this is the standard definition for metric spaces, and when q=∞q = \infty this corresponds to d(x,z)≤max⁡(d(x,y),d(y,z))d(x,z) \leq \max (d(x,y), d(y,z)), which is the definition for ultrametric spaces. They show that VP (Vantage Point) trees, which are intuitive data structures for nearest neighbor search in metric spaces, will speed up in qq-metric spaces. Particularly, they also show that the search time for an ultrametric VP tree is bounded by the depth of the tree. Further, they provide a projection operator that converts points with an arbitrary distance measure into an ultrametric while preserving the nearest neighbors. A projection of the original dataset with this operator is then used in conjunction with a learned map applied to any query point for ANN search. They also show experimentally that their method is competitive with existing ANN search techniques.

Critical strengths

Paper is easy to follow and the technique is simple enough that it can understood well by a good fraction of practitioners. I imagine a github repo with this code has potential to become popular among users.

Critical weaknesses

None

Questions for authors

Please take care of citations. There are a few redundant citations like:

Indyk, P. and Motwani, R. (1998a), Indyk, P. and Motwani, R. (1998b)

Segarra et al., 2019; 2020. Here 2019 is arxiv but 2020 is ICASSP. But actually they have an updated v2 which is 2025 with an updated title that you are referring. Clearly distinguish what is cited from which paper and for what results.

1 comment

We thank the reviewer for the encouraging comments.

Redundant and Outdated Citations

Thanks for pointing this out. We will update citations accordingly.

Public GitHub Repository

The reviewer suggests that a GitHub repository has potential to become popular among users. We agree and are currently working on the legibility and reusability of our code for uploading into a GitHub repository.

We are preparing the repository to follow the manuscript’s structure. To that end, we will provide three main components: (1) A training module where we compute projections and train the q-metric distance estimator. (2) An index construction module. (3) A search module implementing Algorithm 2.

The first module is implemented in PyTorch for compatibility with AI training pipelines. The latter two modules are implemented in C++ for compatibility with search pipelines. All modules have compact implementations which along with the detailed descriptions provided in the manuscript will make the library easy to understand, interpret, and use.

If the manuscript is accepted, we intend to submit a pull request to the Facebook AI Similarity Search (FAISS) repository, which is a widely used library for search. We hope that this will facilitate the adoption of our method and make it more accessible and useful to the research community.

Thanks for this very valuable suggestion.

Link to Anonymous GitHub

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.