Metric $k$-clustering using only Weak Comparison Oracles

AI summary

Overview

• Research area: Unsupervised learning and theoretical metric clustering, specifically clustering under oracle-based models of distance access (the "Rank-model" or R-model) rather than exact pairwise distances.
• Technical level: Advanced. The paper is a theory paper built on metric embeddings, coresets, doubling dimension, noisy comparison sorting, and query-complexity analysis.
• Scope in one sentence: The paper designs randomized algorithms that produce small "Coreset+" summaries for metric k-median and k-means clustering using only a noisy quadruplet comparison oracle, with query complexity that improves when the metric has bounded doubling dimension.

What This Paper Is About

Classical k-clustering algorithms such as k-median and k-means assume they can read off exact pairwise distances, which is unrealistic when similarity is defined by human judgment, a learned model, or an expensive embedding service. This paper studies the R-model, where distances are completely unavailable and the algorithm may only ask a noisy quadruplet oracle questions of the form "is A closer to B, or is C closer to D?". The goal is to output a small set of centers (and a mapping of every item to a center) whose clustering cost is comparable to the optimal k-clustering cost, while using as few oracle queries as possible.

Key Contributions

1. A general-metric algorithm (Alg-G): Constructs an O(1)-Coreset+ for (k,p)-clustering of size O(k polylog n) using O(nk polylog n) queries to the quadruplet oracle, working purely in the R-model with no distance oracle.
2. A doubling-dimension algorithm (Alg-D): Constructs an O(1)-Coreset+ of size O(k polylog n) using only O((n + k²) polylog n) quadruplet queries when the metric has bounded doubling dimension (for example, Euclidean space with a constant number of dimensions).
3. A near-optimal refinement for k-median in doubling metrics (Alg-DI): For the special case of k-median in doubling metrics, the paper obtains an ε-Coreset+ of size O(k polylog n) with the same query complexity, O((n + k²) polylog n), improving the approximation from a constant to 1 + ε for any arbitrarily small constant ε ∈ (0, 1).
4. A lower bound in the R-model: In Appendix A, the authors show that at least 2k − 1 centers are necessary to obtain any o(n)-approximation algorithm for k-median or k-means in the R-model, which motivates returning slightly more than k centers.

Main Findings

• Bypassing the prior impossibility: Galhotra et al. (2024) showed that no o(n)-approximation is possible for k-median and k-means without distance information, which motivated the Rank-Measure (RM) model that adds a distance oracle. This paper shows that constant-factor clustering is still achievable in the pure R-model, provided the output uses O(k polylog n) centers instead of exactly k and a mapping is supplied.
• Center count and query count trade-off: The new algorithms return Õ(k) centers, compared with k centers for the RM-model algorithms of Galhotra et al. (2024) and Raychaudhury et al. (2025), and Õ(nk²) queries for the earlier R-model k-center algorithm of Addanki et al. (2021). The new query counts are Õ(nk) for general metrics and Õ(k² + n) for doubling metrics.
• Improvement over the closest prior work: Raychaudhury et al. (2025) achieved Õ(nk) quadruplet queries plus Õ(1) distance queries in general metrics, and Õ(k² + n) quadruplet queries in doubling metrics, but their techniques cannot construct coresets for k-median or k-means in the R-model because an exact distance oracle is necessary. This paper removes the distance oracle entirely.
• Noisy oracle, not just a perfect one: The results hold for a probabilistic quadruplet oracle that errs with probability at most φ ∈ [0, 1/4), with the "persistence" property that repeated calls on the same edge pair return the same answer and swapping the edge order flips the answer. The authors state that most of their results also extend to the adversarial noise model, though they focus on the probabilistic case.
• Coreset+ is a stronger object than a coreset: An α-Coreset+ is a set C together with a mapping M: V → C such that the total p-th power distance from each vertex to its assigned center is at most α times OPT_k^p. The authors note that any O(1)-Coreset+ directly yields an O(1)-coreset, and an ε-Coreset+ converts to a (k, ε)-coreset by weighting each center by the number of vertices mapped to it.
• Ranking subroutine with bounded dislocation: Lemma 2.1 states that the ProbSort algorithm outputs an ordering of any edge set X with maximum dislocation O(log n) using O(max(|X|, n) log n) queries, succeeding with probability 1 − n^{−4/3}.
• Adversarial sorting subroutine: Lemma 2.2 states that AdvSort, a modification of randomized QuickSort, outputs a (1 + μ)²-sorted sequence using O(m polylog n) queries with probability 1 − n^{−4} under an adversarial quadruplet oracle with noise μ ≥ 0.
• Filtering guarantee: In each round of Alg-G, the filtering step produces a set V_i′ that satisfies |V_i′| ≥ (3/5)|V_i| and ensures that every surviving vertex v is farther from every sample vertex s than the kernel radius r_s of s.
• Emulating an adversarial oracle from a noisy one: The paper shows that when specific structural conditions hold, a test procedure (Alg-Tester) built on comparisons against the smaller kernel answers the quadruplet question correctly whenever the two distances differ by more than a factor of 2, which behaves like an adversarial oracle with error μ = 1.
• Not reported in the provided content: The excerpt contains no empirical experiments, datasets, or benchmark measurements; the contributions are theoretical query-complexity and approximation guarantees.

Methodology in Plain English

The starting point is the classical "sampling property" of k-median clustering: if you draw a random sample of about k polylog n points, then most points are close to the sample, and only a small "bad" set stays far away. The textbook algorithm repeatedly samples points, orders all vertices by distance to the sample, deletes a chunk of the closest half, and recurses; the union of all samples plus the leftovers is a compact summary (a Coreset+) of the whole dataset.

The obstacle is that in the R-model there are no distances, only noisy "which pair is closer?" answers, so the vertices cannot simply be sorted by nearest-neighbor distance. The authors work around this with two samples per round: a first sample S_i^(1) that plays the classical role, and a second sample S_i^(2) used to build, for each point s in S_i^(1), a small "kernel" set of very close points and a disjoint "guard" set of slightly farther points (each of size Θ(log n)). Comparing every active vertex against the guard points produces a "proximity score" per sample point; vertices that are too close to some sample point are filtered out, leaving a set that is guaranteed to be large enough while being far enough away from the samples to be handled reliably.

For the remaining vertices, the algorithm finds approximate nearest neighbors by comparing them against the kernels, ordering the resulting edges with the AdvSort routine. A built-in test uses the smaller kernel as a reference point so that comparisons are only trusted when the two distances differ by more than a factor of 2 — effectively simulating an adversarial oracle with μ = 1. The doubling-dimension algorithm (Alg-D) replaces the expensive exhaustive comparisons with the additional structure that a low intrinsic dimension provides, cutting queries to O((n + k²) polylog n), and Alg-DI refines the result to an ε-Coreset+ for k-median at the same query cost.

Why This Matters

• Research impact: The paper removes the need for a strong exact-distance oracle that was central to prior RM-model work, showing that a noisy comparison-only oracle suffices for constant-factor k-median and k-means clustering. It also quantifies the price of this: the output may need O(k polylog n) centers rather than k, consistent with the paper's own lower bound of 2k − 1 centers for any o(n)-approximation.
• LLM-based oracles: The paper explicitly frames a quadruplet oracle as something that can be realized by presenting two candidate pairs inside a fixed prompt to a large language model and asking it to return a categorical judgment about which pair is more similar.
• Embedding services: A second natural realization is to compute embeddings for each object individually and compare similarity scores for two pairs, returning whichever pair looks more similar.
• Crowdsourced or learned oracles: A dedicated quadruplet oracle can be trained with learning-to-rank methods on annotated data, where the labels themselves may come from crowdsourcing, as cited (Liu et al., 2009).
• Reducing human annotation burden: The paper's MNIST example illustrates the practical payoff: if a few hundred representative images are extracted along with a good mapping, human annotators only need to label those few hundred, and the mapping automatically assigns the remaining images to the right cluster.
• Industry relevance: Because LLM and embedding-service calls carry a direct financial cost per access, the paper's emphasis on both query complexity and bounded noise directly address the cost and reliability constraints of deploying clustering over real data pipelines.
• Computational bottleneck relief: The authors note that obtaining exact distances can itself require solving an NP-hard problem, so eliminating distance queries removes a potential computational bottleneck, not just a financial one.

Future Directions

• Closing the center-count gap: The paper proves at least 2k − 1 centers are needed for any o(n)-approximation in the R-model, while its algorithms return O(k polylog n) centers; determining the true optimal number of centers between these bounds remains open.
• Extending beyond constant p: The technical overview focuses on the k-median objective (p = 1) and states that the approach extends naturally to any constant p > 1, leaving the precise behavior for other objectives to be pinned down.
• Adversarial noise in full detail: The authors state that most of their results extend to the adversarial noise model but that they focus on the more challenging probabilistic case, so a complete adversarial treatment is a natural follow-up.
• Bridging theory and practice: The paper positions LLM-derived and embedding-derived oracles as the motivating implementations, but the provided content reports no experiments measuring how real oracles behave against the φ < 1/4 noise assumption, leaving empirical validation as an open step.
• Applications to other oracle-based problems: The authors note that oracle models have been studied for hierarchical clustering (Emamjomeh-Zadeh & Kempe, 2018; Chatziafratis et al., 2018; Ghoshdastidar et al., 2019) and correlation clustering (Ukkonen, 2017; Silwal et al., 2023), suggesting the comparison-only approach may transfer to those settings.

Target Audience

• Theoretical computer scientists and machine learning theorists working on clustering, coresets, metric embeddings, doubling dimension, or query complexity.
• Researchers in oracle-based and interactive learning, particularly those familiar with the RM-model, optimal-cluster queries, or noisy comparison sorting.
• Practitioners building LLM- or embedding-based similarity pipelines for large-scale data, who need guarantees about how much noise and cost they can tolerate.
• Graduate students and advanced undergraduates with background in algorithms and metric spaces looking for a concrete example of how a noisy weak oracle can replace exact distance access.

Authors’ abstract

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 \emph{Rank-model (R-model)}, where access to distances is entirely replaced by a \emph{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 \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$-clustering cost. Our method achieves a query complexity of $O(n\cdot k \cdot \mathsf{polylog}(n))$ for arbitrary metric spaces and improves to $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+\varepsilon$, for any arbitrarily small constant $\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.