# Metric k-clustering using only Weak Comparison Oracles

arXiv: https://arxiv.org/abs/2601.19333 · HTML: https://mlsanity.com/paper/2601.19333/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 43 of its 79 references that are in the map.
- First posted on arXiv 27 Jan 2026.

## Builds on (most cited first, 30 of 43)

- [Algorithms with Predictions](https://mlsanity.com/paper/2006.09123/) (2020)
- [Metric Learning for Individual Fairness](https://mlsanity.com/paper/1906.00250/) (2019)
- [Coresets for Clustering with Fairness Constraints](https://mlsanity.com/paper/1906.08484/) (2019)
- [On the Dimensionality of Word Embedding](https://mlsanity.com/paper/1812.04224/) (2018)
- [Learning-Based Low-Rank Approximations](https://mlsanity.com/paper/1910.13984/) (2019)
- [Clustering with Noisy Queries](https://mlsanity.com/paper/1706.07510/) (2017)
- [Clustering with Same-Cluster Queries](https://mlsanity.com/paper/1606.02404/) (2016)
- [Learning-Augmented k-means Clustering](https://mlsanity.com/paper/2110.14094/) (2021)
- [Query Complexity of Clustering with Side Information](https://mlsanity.com/paper/1706.07719/) (2017)
- [The Power of Uniform Sampling for Coresets](https://mlsanity.com/paper/2209.01901/) (2022)
- [Noise-tolerant, Reliable Active Classification with Comparison Queries](https://mlsanity.com/paper/2001.05497/) (2020)
- [Hierarchical Clustering with Structural Constraints](https://mlsanity.com/paper/1805.09476/) (2018)
- [Coresets for Clustering in Excluded-minor Graphs and Beyond](https://mlsanity.com/paper/2004.07718/) (2020)
- [Same-Cluster Querying for Overlapping Clusters](https://mlsanity.com/paper/1910.12490/) (2019)
- [Learning-Augmented Algorithms for Online Linear and Semidefinite Programming](https://mlsanity.com/paper/2209.10614/) (2022)
- [Learning-augmented Maximum Independent Set](https://mlsanity.com/paper/2407.11364/) (2024)
- [Adaptive Hierarchical Clustering Using Ordinal Queries](https://mlsanity.com/paper/1708.00149/) (2017)
- [Query K-means Clustering and the Double Dixie Cup Problem](https://mlsanity.com/paper/1806.05938/) (2018)
- [Learning-Augmented Streaming Algorithms for Approximating MAX-CUT](https://mlsanity.com/paper/2412.09773/) (2024)
- [Approximate Clustering with Same-Cluster Queries](https://mlsanity.com/paper/1704.01862/) (2017)
- [Foundations of Comparison-Based Hierarchical Clustering](https://mlsanity.com/paper/1811.00928/) (2018)
- [Parallel Algorithms for Select and Partition with Noisy Comparisons](https://mlsanity.com/paper/1603.04941/) (2016)
- [Metric Clustering and MST with Strong and Weak Distance Oracles](https://mlsanity.com/paper/2310.15863/) (2023)
- [Learning-Augmented Hierarchical Clustering](https://mlsanity.com/paper/2506.05495/) (2025)
- [Crowdsourced correlation clustering with relative distance comparisons](https://mlsanity.com/paper/1709.08459/) (2017)
- [Comparison Based Learning from Weak Oracles](https://mlsanity.com/paper/1802.06942/) (2018)
- [Rk-means: Fast Clustering for Relational Data](https://mlsanity.com/paper/1910.04939/) (2019)
- [Relaxed Oracles for Semi-Supervised Clustering](https://mlsanity.com/paper/1711.07433/) (2017)
- [Relational Algorithms for k-means Clustering](https://mlsanity.com/paper/2008.00358/) (2020)
- [Learning to Generate Fair Clusters from Demonstrations](https://mlsanity.com/paper/2102.03977/) (2021)

## Abstract (arXiv)

Clustering is a fundamental primitive in unsupervised learning. However, classical algorithms for k-clustering (such as k-median and 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 input items, we design randomized algorithms that, using only a noisy quadruplet oracle, compute a set of O(k · mathsfpolylog(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-clustering cost. Our method achieves a query complexity of O(n· k · mathsfpolylog(n)) for arbitrary metric spaces and improves to O((n+k2) · mathsfpolylog(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+varepsilon, for any arbitrarily small constant varepsilon∈(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.