Metric k k -clustering using only Weak Comparison Oracles

Rahul Raychaudhury, Aryan Esmailpour, Sainyam Galhotra, Stavros Sintos · 2026

Read Metric k k -clustering using only Weak Comparison Oracles by Rahul Raychaudhury, Aryan Esmailpour, Sainyam Galhotra, Stavros Sintos (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2601-19333.txt.

Introduction

Rahul Raychaudhury and three co-authors cluster data when exact distances are out of reach. Clustering groups like items together and powers much of unsupervised learning. Classic methods assume they can read exact pairwise distances, which many modern settings cannot supply.

Their setting gives only weak comparison oracles: answers that say which of two distances looks bigger, with noise and limits. Algorithms that cluster from comparisons alone could work where numbers are untrusted or private. The work tests how far ranking style information can carry a classic task that was built for exact numbers from the start.

Catalog record

CREATORRahul Raychaudhury, Aryan Esmailpour, Sainyam Galhotra, Stavros Sintos
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE130 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2601-19333

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Metric k k -clustering using only Weak Comparison Oracles Rahul Raychaudhury, Aryan Esmailpour, Sainyam Galhotra, Stavros Sintos Abstract Clustering is a fundamental primitive in unsupervised learning. However, classical algorithms for k k -clustering (such as k k -median and k k -means) assume access to exact pairwise distances—an unrealistic requirement in many modern applications. We study clustering in the Rank-model (R-model) , where access to distances is entirely replaced by a quadruplet oracle that provides only relative distance comparisons. In practice, such an oracle can represent learned models or human feedback, and is expected to be noisy and entail an access cost. Given a metric space with n n input items, we design randomized algorithms that, using only a noisy quadruplet oracle, compute a set of O ⁡ ( k ⋅ 𝗉𝗈𝗅𝗒𝗅𝗈𝗀 ⁡ ( n ) ) O(k\cdot\mathsf{polylog}(n)) centers along with a mapping from the input items to the centers such that the clustering cost of the mapping is at most constant times the optimum k k -clustering cost. Our method achieves a query complexity of O ⁡ ( n ⋅ k ⋅ 𝗉𝗈𝗅𝗒𝗅𝗈𝗀 ⁡ ( n ) ) O(n\cdot k\cdot\mathsf{polylog}(n)) for arbitrary metric spaces and improves to O ⁡ ( ( n + k 2 ) ⋅ 𝗉𝗈𝗅𝗒𝗅𝗈𝗀 ⁡ ( n ) ) O((n+k^{2})\cdot\mathsf{polylog}(n)) when the underlying metric has bounded doubling dimension. When the metric has bounded doubling dimension we can further improve the approximation from constant to 1 + ε 1+\varepsilon , for any arbitrarily small constant ε ∈ ( 0 , 1 ) \varepsilon\in(0,1) , while preserving the same asymptotic query complexity. Our framework demonstrates how noisy, low-cost oracles, such as those derived from large language models, can be systematically integrated into scalable clustering algorithms. 1 Introduction Clustering is a fundamental problem in unsupervised learning. Traditional methods like k -center, k -median, and k -means all rely on computing pairwise distances. For their output clusters to be meaningful, these distances must reflect the user’s notion of semantic similarity. However, designing such tailored distance measures is especially difficult for complex data like images. Even when a distance function is well defined, evaluating distances between certain types of objects can be prohibitively expensive. Motivated by these challenges, there has been a long line of work that avoids direct distance computations and instead uses oracles . Oracles serve as abstractions for machine learning models or human feedback that provide partial information about the relative distance between the points. Oracle-based models have been studied for k -clustering Bateni et al. 2024 ; Braverman et al. 2025a ; Addanki et al. 2021 ; Galhotra et al. 2024 ; Raychaudhury et al. 2025 , hierarchical clustering Emamjomeh-Zadeh & Kempe 2018 ; Chatziafratis et al. 2018 ; Ghoshdastidar et al. 2019 , correlation clustering Ukkonen 2017 ; Silwal et al. 2023 among others. In this paper, we study clustering in the Rank-model (R-model), where pairwise distances are inaccessible. Instead, one has access to a noisy quadruplet oracle, a function that, given two pairs of input items (A,B) and (C,D) , answers the question: “Is A closer to B , or is C closer to D ?” . Intuitively, quadruplet queries are easier than direct distance queries because they are inherently local and require only relative comparisons, compared to distances which are global. Quadruplet queries are also more practical than the commonly studied optimal-cluster queries, which must return the correct clusters for the queried points. In practice, a quadruplet oracle can be realized in several ways. A natural option is to leverage a large language model (LLM). For instance, two candidate pairs can be presented within a fixed prompt that specifies the intuitive similarity metric of interest, and the model is then asked to return a categorical judgment. Another option is to use an online embedding service: embeddings are computed for each object individually, and the oracle’s decision is obtained by comparing similarity scores for pairs (A,B) and (C,D) , returning whichever pair appears more similar. A further possibility is to train a dedicated quadruplet oracle using learning-to-rank methods on annotated data Liu et al. 2009 , where the labels themselves may come from crowdsourcing. Regardless of the implementation, we generally expect the oracle to be noisy and to have some cost associated with access. For example, with embedding-based oracles, accuracy depends on how well the embedding space aligns with the semantic notion of similarity. In terms of access costs, LLMs and embedding services incur a direct financial cost. The study of clustering in the R-model was initiated by Addanki et al. 2021 , who considered problems such as k -center and hierarchical clustering. Subsequently, Galhotra et al. 2024 showed that no o(n) -approximation, where n is the number of items in the metric space, is possible for k -median and k -means clustering without distance information and introduced the Rank-Measure (RM) model: Along with a quadruplet oracle, they allow access to a distance oracle that returns the exact distance between two input items. They further established several results in this setting. Recently, Raychaudhury et al. 2025 , showed that k -clustering is possible in the RM-model using O(nk\,\mathsf{polylog}\,n) quadruplet queries and only O(\mathsf{polylog}\,n) distance queries. When the doubling dimension of the input metric space is bounded, they further improve the quadruplet queries to O((n+k^{2})\mathsf{polylog}\,n) while distance queries remain O(\mathsf{polylog}\,n) . These query complexities are near-optimal within logarithmic factors. Although these results provide strong guarantees, two challenges remain. First, in practice, a strong distance oracle may just not be available to evaluate distances accurately. Second, it is critical in prior work to interleave distance queries with quadruplet queries, which can be problematic. For example, obtaining exact distances may itself require solving an \mathsf{NP} -hard problem, creating a computational bottleneck. Motivated by these considerations, in this paper, we ask, what is the best we can do in the context of clustering problems having access only to a noisy quadruplet oracle? In Appendix A , we show that at least 2k-1 centers are necessary to obtain any o(n) -approximation algorithm for k -median/means clustering in the R-model. Hence, we ask the following questions: “Can we compute a k -clustering in the R-model with only O(k\,\mathsf{polylog}\,n) centers and a mapping from each item to a center, using O(n\,k\,\mathsf{polylog}\,n) quadruplet queries, such that the clustering cost is comparable to the optimal cost with k centers?” In many practical settings, the data live in high dimensions but have low intrinsic complexity (e.g., small doubling dimension) Yin & Shen 2018 ; Nakis et al. 2025 ; Ng & Zhang 2002 ; Tenenbaum et al. 2000 . For example, Euclidean space with a fixed number of dimensions is a metric space with a constant doubling dimension. A natural question is whether this additional structure may be beneficial. Specifically, we ask “When the intrinsic dimensionality is small, can we reduce the query complexity to O(n\,\mathsf{polylog}\,n) ? Moreover, can we improve the approximation quality while still relying solely on quadruplet queries?” In this paper, we provide affirmative answers to both questions. We note that having such a small set of centers along with a mapping function is very useful in practice, as it shifts the burden of clustering to a substantially smaller set. For

Read the complete text