Metric $k$-clustering using only Weak Comparison Oracles
Authors: Rahul Raychaudhury
Aryan Esmailpour
sainyam galhotra
Stavros Sintos
Venue: ICLR 2026 Poster (2026)
Keywords: clustering
$k$-center
$k$-median
$k$-means
comparison oracles
learned rankers
learning-augmented algorithms
Primary area: learning theory

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, which is 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.

Published as a conference paper at ICLR 2026
METRIC K- USING ONLY WEAK COMPAR- ISON ORACLES
Rahul Raychaudhury' Aryan Esmailpour University of Illinois Chicago
Sainyam Galhotra 3 Cornell University
Stavros Sintos?
Duke University
ABSTRACT
Clustering is fundamental primitive in unsupervised learning. However, clas- sical algorithms for k-clustering (such as k-median and k-means) assume access to exact pairwise distances, which is an unrealistic requirement in many modern applications. We study clustering in the Rank-model (R (R-model), where access 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 metric space with input items, design randomized algorithms that, using only a noisy quadruplet oracle, compute a set of O polylog(n)) centers along with 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 query complexity of O(n k polylog(n)) for arbitrary met- ric spaces and improves to ( + k²)- polylog(n)) when the underlying metric has bounded doubling dimension. When the metric has bounded doubling dimen- sion we can further improve the approximation from constant to 1 + E, for any arbitrarily small constant e E (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.
INTRODUCTION
Clustering is 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 's notion of semantic similarity. However, designing such tailored distance measures is especially difficult for complex data like images. Even when distance function is well defined, evaluating distances between certain types of objects can be prohibitively expensive.
Motivated by these challenges, there has been long line of work that avoids direct distance com- putations 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 [Btenni et al. (2024): Braverman et al. (025a);; Addanki et al.] (2021): Galhotra et al. (2024); Raychaudhury et (2025). hicrarchical
clustering Smamjomeh-Zadee & Kempe (2018): Chatziafratis et al. (2018); Ghoshdastidar et al. 2019)) correlation clustering [kkonen (2017); Silwal et al. (2023) among others.
In this paper, we study clustering in the Rank-model (R-model), where pairwise distances are inac- cessible. 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?". In- tuitively, 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, quadruplet oracle can be realized in several ways. natural option is to leverage a large language model (LLM). For instance, two candidate pairs can be presented within 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 em- bedding service: embeddings computed for each object individually, and the oracle's 's decision

---

Published as a conference paper at ICLR 2026
is obtained by comparing similarity scores for pairs (A, and (C, returning whichever pair appears more similar. A further possibility is to train a dedicated quadruplet oracle using learning- to-rank methods 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-basee 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. (202 who considered problems such as k-center and hierarchical clustering. Subsequently, Galhotra et al. (2024) showed that no (nl-approximation where π 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, RRaychaudhrry et al. (2025), showed that k-clustering is possible in the RM-model using Onk polylog ni) quadruplet queries and only O(polylog n)) distance queries. When the doubling dimension of the input metric space is bounded, they further improve the quadruplet queries to ((nn + k²) polyyog n.) while distance queries remain Oppolylogn). 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 NP-hard problem, creating computational bottleneck. Motivated by these considerations, in this paper, we ask, what is the best we can do for clustering when we have 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) approximatin algorithm for k-median/means clustering the R-model. Hence, we ask the following questions:
"In the R-model, can compute set of Olk polylogn) centers and a mapping from each item to a center, using On 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 high dimensions but have low intrinsic complexity (e.g.. small doubling dimension) Nakis et al. (2025); Roweis & Saul (2000); Tenenbaum et al. (2000). For example, Euclidean space with a fixed number of dimensions is a metric space with a con- stant 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 polylog n)? Moreover, can we improve the approximation quality?"
In this paper, provide affirmative answers to both questions. We emphasize that algorithms do not directly output exactly ht centers. Instead, they return a set of O(k polylog n) centers together with assignment of every input point to one of these centers, yielding a clustering whose cost is within a constant factor of the optimal k-clustering cost. We note that having such a small set of centers along with mapping function is very useful in practice, as it shifts the burden of clustering to a substantially smaller set. For instance, consider clustering MNIST digits 0,...,9. 9. If one can extract representative subset of only a few hundred images along with a good mapping, then human annotators would only need to identify the correct class of these, while the mapping automatically ensures that the remaining images are mapped to the correct cluster. Next, we present the formal setting and summarize our contributions.
1.1 PROBLEM SETUP AND CONTRIBUTIONS
We require some preliminary definitions before formally presenting the model and our results. Let Σ (V, d) be a finite metric space with d : V V V Rzo- We consider metric spaces with |V| n. Any such space can be viewed as a weighted complete graph. We use to denote the set of all edges between vertices in V. The doubling dimension dim(E) is the smallest 5 such that every ball of radius p can be covered by 2 balls of radius p/2. We say Σ has bounded doubling dimension dim(E) & 5n for some fixed constant dn-
2

---

Published as a conference paper at ICLR 2026
Clustering Cost. For E V and U V, define d(v. U) min d(v, u). Let k. E Σz1. For U. W. S V. let ( = (owee(d(ww U}}.. For W S V, the optimal (k, pluusterii cost is (W) = minugv, |i|= ( if W = V. we simply write OPT A 3-approximation algorithm for (k, p) clustering returns set A such that & (V) S 3 OPT.. where 3 Z 1. For p 2 the (k, p) clustering corresponds to k-median and k-means clustering, respectively. Throughout the paper we assume that = O()).
Coresets and Coreset+. Next, we recall the standard definition of coreset and introduce the stronger notion of a Coreset+.
0(1) A set T S V along with a weight function w T R is called an ((1)-coreset for (A, p)clusterrnn if any subset A S T such that |A| = k and ET A)) s B: IU] Exer (tt)( U)}² satisfies COST (V) S ( OPT
(k, -cooreset:: For a real number E E (0, a set T S V along with a weight function w : V - Rso is called a c)oorett for (k, plllusteing if for any subset A S V with |A] k. it holds that (1 C)COST (V) s (d)((t
& (1 + e)COST
Coreset+: For positive real number a, set C S V together with mapping M V C is called an a-CCrreet+ if Eeev(((e. S OPT
It follows from well-known results (e.g.. Har-Peled & Mazumdar (2044; Chen 2009 that any Coreeetttte directly yields an cooreet:::::: define the weight function w R by
((c) Evev (M(() c}- Furthermore, for p = 1, it follows that an e-Coreset+ can be converted to (ks, cc-oreset in the same way.
R-model. In the R-model, direct access to the distance function d is unavailable. Instead, all distance-related information must be obtained through a noisy quadruplet oracle. Formally, for an emorr parameter yo E [0, 1). quadruplet oracle with probabilistic noise yp is function @ & {YES, }o} that, given two edges e1, e2 E E, where {V1, v2), and e2 {v3, v1). outputs
Ō(er, e2) = YES, with probability at least 4: if d(v1, v2) S d(v3, No, with probability at least sp, if d(vi, v2) > d(v3, v4).
In other words, the oracle fails identify the closer pair with probability at most sp Furthermore, the randomness is independent across distinct queries and is fixed once per edge pair; thus, repeated calls to @(e e²) always return the same result, and flipping the order of the edges always flips the answer. This property referred as persistence.
Our Results. As a warm-up, in Appendix A we show that at least 2 to obtain any approxiaixiinnonnnn algorithm for k-meddan/mmeans clustering in the R-model. On the other hand, we obtain the following positive results for clustering in the R-model.
1 centers are necessary
General
Doubling
centers
queries
centers
queries
Galhotra al. 2024
k
O(nk). O(k2)
O(nk). O 0012 n)) Õ(1)
RM-model
Raychaudhury et al. 2025
k
Ö(nk), Ö(1)
k:
Addanki al. 2021
k O(nk22)
k:
O
R-model
NEW
O(k)
((nk)
O(k)
O(K2 +n)
Table 1: Comparison of our algorithms for k-clustering in the R-model with known clustering algo- rithms in the R-model and RM-model general and doubling metric spaces. They all O(1)-
approximation algorithms. For every algorithm we show the number of centers it returns and the number of oracle queries it executes. In the RM-model, the first (resp. second) quantity in the column queries shows the number of queries to the quadruplet (resp. distance) oracle. The no- tation (--) hides polylog (n) factor. Galhotra et al. 20024); Raychaudhury et al. (2025) studied k-median/mmeans clustering. [dddnki et al. (2021) only studied the k-center clustering in the R- model however their algorithm only holds if the optimal clusters are of size (2(v)..
For general metric spaces, we give an algorithm that constructs an Core-Cte for (k,p)- clustering of size Okkpolylog n), using (nkkoolyoogn) n) queries the quadruplet oracle.
3

---

Published as a conference paper at ICLR 2026
For metric spaces with bounded doubling dimension (for example, the Euclidean space with con- stant number of dimensions), we design an algorithm that constructs an (11)-Coreset+ of size (kpolylog n), using only O(1 k²) polylog n) quadruplet queries.
For the special case of k-median in doubling metrics, we further obtain an e-Coreset+ of size O (kpolylog n) with the same query complexity, i.e., O((n po)polylogn).
Our main results and the comparison with other known algorithms in the RM and R-model are shown in [
1.2 RELATED WORK
Due to the large body of related work, we focus mostly clustering problems under related oracle- based models. We discuss additional related work in Appendix E
Addanki al. (202T) initiated the study of k-center clustering with access quadruplet oracle. In the R-model (with probabilistic noise), they developed an algorithm under structural assumptions on the optimal clustering. To the best of our knowledge, this remains the only prior work clustering under purely the R-model.
More recently, Galhotra et al. (0224) showed that even with perfect quadruplet oracle, no O(1)-
approximation is possible for k-means or k-median without distance queries. This motivated their weak-strong framework: weak oracle provides inexpensive quadruplet comparisons. while a strong oracle supplies exact distances at higher cost. Within this framework, they designed O(1)- approximation algorithms for k-center, k-median, and k-means in general metric spaces, achiev- ing query complexities of O(nk polylog n.) to the quadruplet oracle and Ol-22 n) to the dis- tance oracle. a follow-up work. RRaychaudhury et al. (2025) improved the number of calls to the distance oracle from pkolpoly n) to Oppolylo n.). They also study clustering problems in metric spaces with bounded doubling dimension, designing (11) aapproximation algorithms with O(nn + +k> polyloo n) calls to the quadruplet oracle and O (polylog n) calls to the distance cle. Specifically, for k-center clustering [Raychaudhury et al. (2025) construct (oo)-ceeeset of size Okpolyyog n1) executing (nkkoolylog n.) (resp. O((n + kpoolyy n) in doubling metrics) queries to the quadruplet oracle (R-model). However, using their techniques, no coreset construction for k-median or k-means can be constructed in the R-model, i.c., an exact distance oracle necessary.
Independently, Bateni et al. (2024) investigated k-clustering and the MST problem in general metrics under related weak-strong framework. Their strong oracle matches that of Galhotra et (2024), but their weak oracle differs: given v V, it outputs d(u, v) with probability at least 1 and an arbitrary value otherwise. They obtained ((1) ((1))-aproximmtion) k-means using Onk polylog n) weak queries and O(k² O(k2polylog n) strong queries. Under the same strong-weak model, Braverman al. (025a) studied coresets for clustering problems.
for k-center, k-median, and
There is rich line of work on approximate sorting with probabilistic comparison oracle. In this model, well-known that the maximum dislocation cannot be improved beyond Oloog n); in particular, no algorithm can guarantee that every element is placed within o(log n)) positions of its true rank. After a series of results Braverman & Mossel (008); Braverman et al. (2016); Geissmann et al. 2017 2020 it recently shown in Geissmann et al. (2025) that O n) dislocation can be achieved with On log n) queries with high probability, when the noise o < 1/4.
2 TECHNICAL PRELIMINARIES
Let Σ (V,d) be a metric space with d V + Rzo- We consider finite metric spaces with M n. Any finite metric space can be viewed as weighted complete graph, and we often use graph terminology. For U,W C V, let E(U, W) ((u,w) u U, w E W, u * w). and {(U) = E(U, U). For an edge set X, let V(X) denote the set of vertices incident to edges in X. For e = [u,v] E &VV., we define d(e) == v(u,v). For U, W C V and u E U, define (us U) nearest-neighbor distance to W.
+ 1xx U d(x, W)
W)H, the position of u when U is ordered by
While in the R-model we do not have access to distances, the quadruplet oracle allows us approx- imately order edges based on their weights (distance). For an edge set X C E, let गy. denote an ordered sequence of the edges in X. For an edge X, we RANKx(e)) to denote its position
4

---

Published as a conference paper at ICLR 2026
among the edges in I when sorted in ascending order of distance. and RANK (e) for its index in Ty. The dislocation of e under Tx. is defined as RRNNKr (e) RANKx(e)]. The maximum dislocation of xx is bounded by D if the dislocation of every edge in X is bounded by D. It is easy to verify that if Ty. has maximum dislocation 'D2 then any subsequence x _ τy also has maxi- mum dislocation at most 'D. The next lemma follows from a straightforward application of result by Geissmann et al. (2025).
Lemma 2.1. Let Σ (V,d) be a metric with |V] n. and = E(V) be its edge set. Suppose & x & - {YES, NO} is a probabilistic quadrupler oracle with noise y [0, 1. There exists an algorithm PROBSORT such that for any X S &, with probability 1 n 44/3 PROBSORT(X)) outputs an ordering Tx with maximum dislocation (lognn using ((max([2{) log queries to Q.
A small bound on the maximum dislocation of Ty ensures that the ranks are approximately pre- served; however, it offers guarantees about the relative magnitudes of edges that appear in the wrong order. For such guarantees, we require a stronger notion of approximate ordering. For an index i [[>]]] let Tx [i] X denote the edge in the i-th position of ıx. For constant a 2 we say Tx is a-sorted, if for all i < j E [[]]], d((xx(i) I a d(Txxi)). While in this paper we study quadruplet oracles under the probabilistic noise model, prior work (see, for example (Addanki et al. 202T also considered weaker adversarial noise model.
Quadruplet Oracle with Adversarial Noise Let μ E Rzg be a constant. A quadruplet oracle with adversarial noise p is a function Q : & x
8 - (YES,No) that, given two edges e₁ {v1, V2]
and e2 = =V33, outputs YES if d(vi, V2) S Ita d(va, v4), No d(vi, v2) 2 (1 + (u) d((3, V4), and an adversarially chosen (non-adaptive) answer whenever the ratio d(v1, v2)/d(v3 M4) lies in the interval [1/(1+ + p), 1 1+ +p].
In other words, the oracle gives the correct response when the edge weights are not relatively close but may be adversarially wrong otherwise. The next lemma shows that under the adversarial noise model, it is possible to compute an ((1)-sorted sequence of edges using the quadruplet oracle.
Lemma 2.2. Let E (V, d) be a metric with Vi = n, & E(V) the edge set, and Q an adversarial quadruplet oracle with noise μ 2 0. There exists an algorithm ADVSORT such that for any X S & of size m, with probability 1 - n -4, ADVSORT(X)) outputs a (1 + -so-terted sequence TX using Om polylog n.) queriex to Q
The proof of I Lemma 2.2 can be found in Raychaudhury et al. (2025) and is based on a similar result by [Acharya et al. (2018). The actual algorithm, ADVSORT, is a slight modification of the classic randomized QUICKSORT algorithm.
Although in this paper work in the probabilistic noise model, in the analysis of our algorithms, show that when certain very specific structural conditions hold, it is feasible to emulate an adversarial quadruplet oracle by appropriate calls the probabilistic quadruplet oracle. In such situations, we will be able to plug in an emulated adversarial quadruplet oracle into ADvSORT to obtain an O(1)- sorted ordering of edges. We discuss more in the technical overview.
TECHNICAL OVERVIEW
Let Σ = d) be metric space accessible in the R-model, i.e., there exists noisy probabilistic quadruplet oracle Q that compares edge weights in E. We assume that the error rate of Q satisfies 1/4. Our goal is to design an algorithm which, given parameters k.p E Zz1 and access to Ô, returns Coreset+ for (k, cluusterni of size Ok polylog For simplicity, we focus on the k-median objective (p- = 1), but our approach extends naturally to any constant p 1.
The remainder of this section is organized as follows. We first describe a generic approach for computing a Coreset+ under perfect quadruplet oracle. We then present our algorithm for general metric spaces, ALG-G, which adapts this high-level strategy to the noisy setting using On kpolylog kpolloyo n) queries. Next, we introduce ALG-D, which further reduces the query complexity to O((n + k²) polylog rı) when Σ has bounded doubling dimension. Finally, we outline refine- ment method, ALG-DI, which takes a Coreset+ returned by the previous algorithm and builds an
For simplicity, we assume all pairwise distances are unique. Most of our results extend to the adversarial model, but we focus the more challenging prohabilistic
case.
5

---

Published as a conference paper at ICLR 2026
e- Coreset+ with (n polylog n) additional queries. Due space constraints, full details and proofs of these algorithms are deferred to Appendix B C and respectively.
Let C* denote an optimal k-median solution, i.e., |C*| and COST (V) OPT Recall that a Coreset+ is defined as set C S V together with a mapping M V + C such that Evev d(v, C) s O(1) OPT for all v E V. The generic algorithm is based on well-known sampling property of k-median clustering Harr-Pled & Mazumdar (2004); Mettu & Plaxton (2002). Suppose we take a random sample S - V of size (5(k polylog n).. We call vertex v V good if d(v, < 2d(v, C*),
and bad otherwise. Let V S V denote the set of bad vertices. It can be shown that, with high probability, [V, = ((V)).
Generic Algorithm. The above sampling property leads to a natural recursive sampling algorithm. Sample a set S S V of Ol polylog vertices, order the vertices in V in ascending order by their wearest-neighbor distance to S, remove constant fraction subset of the first half from V, and recurse. The process continues until there are O polylog n) remaining vertices. The union of all samples across rounds (along with the remaining vertices in the last round) constructs an O(1) -oCrsstt of size O(k polylog rt). The mapping is defined by assigning each vertex v E V to its nearest neighbor among the sampled vertices from the round in which was removed. The main argument is that in any round, there are sufficiently many good vertices in the second half (with larger distances from S) that account for the accidentally removed bad vertices. By careful analysis, one show that across rounds, there exists a bijection between the bad vertices and these good vertices.
At high level, our algorithms ALG-G and ALG-D emulate this approach. However, there are several obstacles. In or- der to succeed, in each round we need map vertices in V to (approximate) nearest neighbors in S before ordering them by distance. Although in the R-model we can order the edges E(S, V) with O(log n.) dislocation using the PROBSORT prim- itive, such an ordering is not sufficient to find approximate nearest neighbors. We need more sophisticated approach.
Overview of ALG-G (Appendix B). The algorithm operates in rounds. Let V; S V denote the set of active vertices in round i. In each round, the algorithm takes two random sam- ples s.D)) and s!²²) of sizes O(k O(klog" n) and O(k log" n) re- spectively. The first sample s(") plays the same role as the sample set in the generic algorithm described above. The second sample set s(2) is used as follows. The algorithm applies the PROBSORT primitive to approximately order the edges X2 = ((S ,S(2)), ((()))) requiring Ok2 polylog n) quadru- plet queries. From this ordering, the algorithm identifies for each s E s two disjoint sets of @(log n) vertices: a kernel sel (S) s!22) and a guard set GUARD,(S) s(2)
Figure I: Let s E s(D) be the green vertex. The vertices in KERNEL;(S) are shown in red, and those in GUARD,(S) are shown in blue. All remaining vertices in V are depicted black points. The combined set KERNEL; U GUARD,(S) consists of vertices that are close to in rank relative to all vertices in V, with those in (ERNEL, being closer to than those in GUARD, All black vertices inside the red circle will be filtered out. No vertex outside the blue circle will be filtered out. Some vertices between the red and blue circles may be filtered out.
These sets satisfy the following properties:
(i) For every s E 5(1)) and every V E (ERNEL((S) U [V.] (U) PVS,(v, Vi) S pepolllggn
(ii) For every 5(2) any (S)RD,(s), d(s, w) < d(s.g).
KERNEL,(S), and any g
The first property implics that for any s E s.1) vertices in both (ERNEL;(S) and (U) are very close to in terms of rank. The second property ensures that kernel vertices are strictly closer than their respective guard vertices. An example of a kernel and guard set is shown in Figure [ These sets play complementary roles: guard vertices are used to filter all vertices from V, that are too close to S (!)), while kernel vertices are used to compute approximate nearest neighbors in ( for the rest of the vertices.
Filtering. Next, the algorithm for each v E V; \ (5 U s(())) and s E s(",, compares against the guard vertices compute proximity scores:

---

Published as a conference paper at ICLR 2026
PCOUNT&(V)=
Σ
1(8((s, v) {s,g)) returns "d((s s d(s.
(EGUARD:())
Based on these scores, the algorithm computes subset V = {v E V, (s U s.! max max)e PCOUNT,(V) < /m where Mwin is a suitable threshold of size Ollo n). Com- puting V requires Onk n) quadruplet queries. Recall that the generic algorithm, in each round, orders vertices based on their nearest neighbor distance the sample and removes a fraction of the first half. In the presence of noise, we cannot find the nearest neighbors of all vertices in V,. It turns out that V has sufficient structural properties for the algorithm to be able find their nearest neighbors in s In the analysis, we show that filtering guarantees that no vertex in V is closer to a sample vertex s E S than the kernel vertices KERNEL; while at the same time not discarding too many additional vertices. Formally, filtering ensures that with high probability, [V] 2 & and Vv E V Vs & d(v,s) > Tss where rs (aX dl(s, w) denotes the kernel radius of s. An example of filtering vertices is shown in Figure
Finding approximate nearest neighbors. The key insight is the following. Consider any two sample vertices 51 Sg E s. and any vertices V1, V2 E V s(?) and suppose the following conditions hold:
(i) d(s1, v1) Ts, and d(s2, v2) > Ts2.
(ii) we know which kernel has the smaller radius, i.e., whether Vss S Tsg or vice versa.
In the analysis, we show that when the above conditions hold, by making appropriate comparisons with the smaller kernel, we can design test procedure that answers whether disi, v1) ) < d((2, v2)- The test is correct with high probability when the two distances differ by more than 2 factor, i.e., d(s).v1) d(s2, vo) > or d(s2, /d)/ V1)= > 2. Observe that this behavior is similar a quadruplet oracle with adversarial noise with error μ 1 (see Section 2). We design a procedure ALG--ESTER (see Section [B.2). based on this test.
Our algorithm runs ADVSORT (see Section 2 with ALG-TESTER as the comparator to order the edges in y/ E(S!") VJ). Whenever ALG- TESTER is asked to compare two edges from yi, the first condition is satisfied by the construction of V". and ALG-TESTER uses the ordering of X; to determine which kernel has smaller radius. By the preceding discussion, on all such queries, behaves akin to an adversarial quadruplet oracle with noise js = 1. This immediately yields a 4-
approximate nearest neighbor in S for every vertex in V/. Each call to ALG-TESTER triggers (log n) quadruplet queries, and ADVSORT calls ALG-TEST TESTER a total of O(k polylog n) times.
The previous step computes an approximate nearest neighbor for each vertex in V; within the set s("). In the next step, the algorithm again applies ADV SORT, as before, to approximately order the vertices in V according to their estimated nearest-neighhor distances, and then identifies a prefix V" S Vy. Intuitively, this set V corresponds to the set of vertices removed by the generic algorithm
in round. The algorithm also maps each vertex in V" to their neighbor in S.1)) found previously. Next, the algorithm recurses on V = V, (V% US! U S?). The process terminates after
Olog r) rounds, at which point we output the set C = UL_ (S Us(( of O(k polylog n) centers that consists of the union of all samples. The mapping function M is defined by the per-round mappings of the sets Vi to the sets S The complete algorithm along with the analysis is available in Appendix B We conclude with the next theorem.
Theorem 3.1. Let Σ = (V, d) be a finite metric space of size V| = n, which is accessible under the R-model. There exists randomized algorithm ALG-G that, given parameters k. Z4, with high probability returns an O(1)- (o1l-Coreset+ for (ks, p)clusttriingg of size Okkpolylog n) using Onk polylog n)) calls to the quadruplet oracle.
When Σ has bounded doubling dimension, we present an algorithm ALG-D (Section C.I that reduces the total number of quadruplet queries to O((n + A²) polylog n.). The algorithm follows a similar recursive-sampling framework as ALG-G. Each round begins by drawing two random samples 5f2) and S and computing the kernel and guard sets for every S. However, in order to achieve the desired query complexity bounds, cannot afford to perform the full filtering and nearest neighbo procedures used ALG-G. Instead,
Overview of ALG-D (Appendix C..
the algorithm proceeds as follows.
7

---

Published as a conference paper at ICLR 2026
Partitioning, We first partition the vertices in () into classes s/ vertices in the same class are close. To do this, we construct a conftict graph G, whose vertex set is s!"), and add edge between any two vertices that close. Closeness is determined using proximity scores derived from the guard sets, as in Equation (I). In the analysis, we show that G3 is O(log n) -degenerate, i.e., every subgraph of G; has a vertex of degree at most Ologg)). It is known that a E-degenerate graph can be properly colored with & + 1 colors using simple greedy algorithm Lick & White 1970). We use such coloring to obtain the classes s(!.1), "...",...,.... s(f.))))
((1xx)) such that no two
Nearest neighbors. Our next goal is to compute approximate nearest neighbors for vertices in V, (s U ) with respect to each class s(1.)) In Raychaudhury et al. (2025) it was shown that given two disjoint sets U, W S V and access to an adversarial quadruplet oracle with noise p., that can answer quadruplet queries of the form ({2)), where e₁ C(U U), e2 &(U, W), one can construct a data structure, such that given a vertex v E W. it returns a subset of size Opooyylg n) containing at least one vertex E U, such that d(w,, u) S O(1) d(w, U). Our plan is to apply this result to each class s(1-)) for each j = :,....Xi.. Xi. where we set U S. s!!.a)
and W = =V;' \ (8 U s.?)). To simulate the adversarial oracle, we again use ALG-TESTER as in the general metric case. However, unlike in ALG-G, we have not pre-filtered close vertices in V; \ (5(2)) (.s( If we apply ALG-TESTER to edges containing such vertices, it is not guaranteed to behave like an adversarial quadruplet oracle. Hence, we adopt
filtering strategy: whenever ALG-TESTER is invoked to compare a pair of edges, we first compute proximity scores to ensure that the vertices are not too close. If a vertex is found to be too close, we discard it. This ensures correctness while avoiding the heavy global filtering step of ALG-G. In the analysis, we show that the overall number of quadruplet oracles required in this step is O(n polylog n.).
Post finding approximate nearest neighbors, we proceed similarly as in ALG-G. The full details are in Appendix C Overall, we get the next result.
Theorem 3.2. Let Σ (V.d) be a finite metric space of size M = with bounded doubling dimension, which is accessible under the R-model. There exists a randomized algorithm ALG-D that, given parameters k. Z.t, with high probability returns an (11)-Coreset+ for (k.p)- clustering of size O(koolylog n) using O(n + polylog n) calls to the quadruplet oracle.
Overview of ALG-DI (Appendix D). When the underlying metric has bounded doubling dimen- sion, we show that, given a Coreset+ consisting of a set C C V and a mapping M : V - com- puted via ALG-G or ALG-D, we can compute an Correset+. (C+ .M++ using only O(n polylog n) additional queries, for k-median clustering.
Consider a vertex 5 E C, and let Ug denote the set of vertices mapped it, i.e., Ug {u V M(u)= = s}. Let a, = max,eu, d(,,s). Suppose we order the vertices in U2 by d(..s) and par- tition them into buckets: Bo has maximum distance ag/n2?, B3 covers (az/n?, 20s/ 2as/n"), J. B2 covers (20,/n2; 40./n²) and so on, doubling the outer radius each time. It is easy to see that there are at most Olog n) buckets since as S 0(1) OPT). Since the doubling dimension is bounded, it is well known that if we had access to such a partition, we could improve the approximation quality by choosing constant number of vertices from each bucket (see, e.g., Har--Hareed & Mazumdar (204 Our high-level strategy is to follow a similar approach. Unfortunately, without access to distances, cannot compute such a partition directly. Our algorithm operates follows.
For every s E C, it first obtains a (11)-sorted ordering of the edges E(s, U.). This does not re- quire any quadruplet queries and can simply be extracted from the post-ANN ordering computed by ALG-D or ALG-G. We then perform a multistep sampling on this order: in the first round, we sam- ple (pooyylo n) vertices from U., in the second round from the last half, then from the last quarter, and so on, halving the suffix each time. Let W2 be all the samples obtained from Ug. Repeating this for all E C accumulates ( polylog n) new samples. We set C+ CUsEC W₃). The algorithm then orders the set Usec E(W,, Uz) using PROBSORT and uses that information to construct new mapping ++ we skip those details here. This step uses O(n polylog n) additional queries.
The crux is the analysis. Although we cannot ensure that we hit every bucket for a E C Cxactlyy we show that our sampling hits relevant distance scales with high probability. We carefully argue that the revised mapping is indeed sufficient.
8

---

Published as a conference paper at ICLR 2026
Method
Cost
Optimal
2.9 104
Ours
3.1 X 104
Baseline
4 x 10
Coresct Points
(h) Our Results
(c) Baseline
Clustering Cost
Figure 2: Comparison of the k-means clustering results obtained by our method against the baseline and the optimal clustering.
Theorem 3.3. Let Σ = (V,d) be a finite metric space of size M = n with bounded doubling di- mension, which is accessible under the R-model. There exists a randomized algorithm ALG-DI that, given a parameter k E L4,, with high probability returns an s-Coreset+ for k-median clustering of size (kpoolyoog n) using O( + 12) polylogn) calls to the quadruplet oracle, where E (0, (0,1) an arbitrarily small constant.
EXPERIMENTS
In this section, we present preliminary experimental results based on a basic implementation of algorithm for k-means clustering. We evaluate the quality of the results obtained from our algorithm, comparing it against the clustering obtained by k-means++ algorithm over the ground truth data points, and the clustering obtained by bascline that always trusts the answers of the noisy quadruplet oracle. The complete descriptions of our algorithm and the baseline are provided later. We refer to the cluster centers obtained from running k-means++ algorithm over the ground truth data as frue centers and the k-means cost of the true centers as optimal cost We use both synthetic and two real datasets whose points are used as the ground truth data the experiments. By default, we simulate the quadruplet oracle with probabilistic noise and set the error rate The oracle has access to the ground truth data and answers correctly with probability 1 - = 0.85. Both the bascline algorithm and our algorithm can only access the data via this noisy oracle and do not have direct access to the ground truth data. The main goal of our experiments is to show the effectiveness of our Coreset+ construction and especially the mapping of the points to the Coreset+ centers. All methods were implemented in Python, and the experiments were conducted using the free version of Google Colab.
0.15.
4.1 EXPERIMENTAL SETUP
Synthetic dataset. For our experiments, we generate a synthetic dataset consisting of two- dimensional points arranged in & 5 clusters of approximately equal size. For each cluster, the points are randomly generated following the Gaussian distribution with a standard deviation equal After generating the data, all the points are randomly shuffled to avoid any relation between ordering and the clusters. Using this procedure, we generate dataset of 10 synthetic points as We use this dataset as the ground truth data in the experiments.
shown in Figure 2
Real datasets. We two real-worke datasets used to evaluate clustering algorithms Braverman eet al.] (2025a); Huang et al. (2019)) the Adult dataset [Beker & Kohavil (1996) and the Defaudr of Credit Card Clients dataset Yeh (2009). For Adult dataset, we use eight numerical attributes, resulting in collection of roughly 50,000 points in 8 dimensions. For Credit dataset, we select nine numerical attributes, resulting in a collection of roughly 30,000 points in 9 dimensions. The values of all attributes are then normalized to be in the range [0, 1]. Similarly to Braverman et al. (2025a), due to computational constraints, we sample 2,000 data points from each dataset using Meyerson sampling [Myyersnn] (200T): We begin with an empty set S and process the points sequentially. The first point is added to S. For each subsequent point, we add to with probability proportional to its distance from the current set S. We employ Meyerson sampling instead of uniform sampling, as its distance-based selection better preserves the geometric structure of the dataset and reduces the risk of underrepresenting smaller clusters.
mmmmn clustering is an NP-hard prohlem, and thus the k-means++ algorithm does not always yield the optimal solution. Nevertheless, we treat the clustering derived from the ground-truth data points optimal.

---

Published as a conference paper at ICLR 2026
(a) Adult
(b) Credit
(a) Adult
(b) Credit
Figure Clustering cost varying
Figure 4: Clustering cost varying yp
Our approach. We first ALG-G from Theorem 3.1 obtain O(1)-Coreset+. Then, as
described in Section [ the obtained centers and the mapping are used to construct an (11)ccoreset: each Coreset+ point gets weight equal to the number of points mapped it. After constructing the weighted coreset, we assume access to a distance oracle, as in the RM-model of [Raychaudhury al. (2025). We then apply k-means++ algorithm on the weighted coreset to obtain the final set of k centers, invoking the distance oracle when necessary.
Baseline. The baseline directly applies the Generic algorithm (Section 3 using the quadruplet oracle. Although the oracle may return incorrect answer with probability yo, the algorithm sumes every response correct and proceeds accordingly. From the returned set of points and the mapping. construct weighted set of centers (coreset) the same manner as algorithm: each sampled center is assigned a weight equal to the number of data points mapped to it. Finally, we k-means++ algorithm the weighted coreset obtain the final & centers, invoking the distance oracle whenever the exact distance between two coreset points is required.
4.2 EXPERIMENTAL RESULTS
Results on synthetic dataset. We observe that the coreset produced by our algorithm contains only 187 points. This corresponds to 98% reduction in size, from the original 10 input points down to just 187 coreset points. Figure 2a shows the set of coresct points. Instead of using the original large dataset, this much smaller coreset is used to obtain the final l centers running the k-means++ algorithm, assuming access to a distance oracle, as described above.
We next evaluate the clustering quality by comparing the results of our algorithm against both the baseline and the ground-truth centers. As shown in Figure the centers identified by our method closely match the true centers (see also Figure 2b) By contrast, the baseline fails to recover some clusters due to erroneous mapping, as illustrated in Figure 2c] leading to noticeably poorer clustering performance. This limitation arises because the baseline unconditionally trusts the noisy oracle during the Generic algorithm. Table 2d] reports the corresponding clustering costs. The k-means cost defined the sum of squared distances from each point its mapped center. Our method achieves a cost within 7% of the optimal solution, while the baseline incurs cost exceeding the optimum by more than 1200%.
Results on real datasets. Next, we compare the clustering cost of our method with both the baseline and the optimal cost on real datasets. In Figure 3 we fix the error rate şp 0.15 and vary the number of clusters & {4, 5, 6, 8}. In both datasets, our method achieves a clustering cost that is very close to the optimum. In contrast, the baseline consistently yields a clustering cost that is 2.5 to 4 times higher than that of our approach. As expected, the clustering cost of all methods decreases as number clusters increases. Finally, in Figure 4 we fix the number of clusters at k 6 and vary the oracle's probabilistic noise level {0.05. 0.1, 0.15,, 0.2, 0.25). As before, both datasets, the clustering cost achieved by our method remains close to the optimum. Moreover, consistent with our theoretical guarantees, the clustering cost of our method is essentially independent of ço. In contrast, the clustering cost of the baseline increases substantially as grows.
5 CONCLUSION
We proposed near-optimal algorithms for constructing coresets for (k, p) cluusterg the R-model. Our results open several directions for future research. First, it is interesting to study whether the techniques can be extended to other clustering objectives (such as hierarchical clustering or sum- of-radi clustering) and to related graph problems (such the Minimum Spanning Tree problem) in the R-model. Second, we plan to generalize our framework to non-men non-metric graphs, to alternative oracle models (such triplet oracles), and different error models.
10

---

Published as a conference paper at ICLR 2026
ACKNOWLEDGMENTS
This work has been partially supported by NSF grants IIS-2348919, IIS-2402823, and grant by Infosys.
REFERENCES
Jayadev Acharya, Moein Falahatgar, Ashkan Jafarpour, Alon Orlitsky, and Ananda Theertha Suresh. Maximum selection and sorting with adversarial comparators. The Journal of Machine Learning Research, 19(1:2227722457 2018.
Raghavendra Addanki, Sainyam Galhotra, and Barna Saha. How design robust algorithms using noisy comparison oracle. Proceedings of the VLDB Endowment, 14(10):10331176, 2021.
Pankaj K Agarwal, Aryan Esmailpour, Xiao Hu, Stavros Sintos, and Jun Yang. Computing a well- representative summary conjunctive query results. Proceedings of the ACM on Management of Data, 2(5): 2024.
Nir Ailon, Anup Bhattacharya, Ragesh Jaiswal, and Amit Kumar. Approximate clustering with same-cluster queries. In 9th Innovations in Theoretical Computer Science Conference (ITCS 2018), volume 94, pp. 40. Schloss Dagstuhl-LeibnnzzZeentne fuer Informatik, 2018.
Hassan Ashtiani, Shrinu Kushagra, and Shai Ben-David. Clustering with same-cluster queries. In Advances in neural information processing systems, pp. 3216-3224, 2016.
MossemadHosseen Bateni, Prathamesh Dharangutte, Rajesh Jayaram, and Chen Wang. Metric clustering and mst with strong and weak distance oracles. In The Thirty Seventh Annual Confer- ence on Learning Theory, pp. 498-550. PMLR, 2024.
Barry Becker and Ron Kohavi. Adult. UCI Machine Learning Repository, 1996.
Lorenzo Beretta, Franco Maria Nardini, Roberto Trani, and Rossano Venturini. An optimal algo- rithm for finding champions tournament graphs. IEEE Transactions on Knowledge and Data Engineering, 35(10):00197-000
2023.
Enrico Bianchi and Paolo Penna. Optimal clustering stable instances using combinations of exact and noisy ordinal queries. Algorithms, 14(2):55, 2021.
Mark Braverman and Elchanan Mossel. Noisy sorting without resampling. In Proceedings of the nineteenth annual ACM-SIAM symposium on Discrete algorithms, pp. 268-276. Society for In- dustrial and Applied Mathematics, 2008.
Mark Braverman, Jieming Mao, and S Matthew Weinberg. Parallel algorithms for select and par- tition with noisy comparisons. In Proceedings of the forty-eighth annual ACM symposium on Theory of Computing, pp. 8-1- 2016.
Vladimir Braverman, Shaofeng H.-C. Jiang, Robert Krauthgamer, and Xuan Wu. Coresets clus- tering in excluded-minor graphs and beyond. In Proceedings of the Thirty-Second Annual ACM- SIAM Symposium on Discrete Algorithms, SODA '21, pp. 2679-2696, USA, 2021. Society for Industrial and Applied Mathematics. ISBN 1781611976465.
Vladimir Braverman, Vincent Cohen-Addad, H-C Shaofeng Jiang, Robert Krauthgamer. Chris Schwiegelshohn, Mads Bech Toftrup, and Xuan Wu. The power of uniform sampling for core- sets. In 2022 IEEE 63rd Annual Symposium Foundations of Computer Science (FOCS), pp- 462-473, IEEE, 2022.
Vladimir Braverman, Prathamesh Dharangutte, Vihan Shah, and Chen Wang. Leaming-augmented augmented maximum independent set. Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 2024.
Vladimir Braverman, Prathamesh Dharangutte, Shaofeng H-C Jiang, Hoai-An Nguyen, Chen Wang, Yubo Zhang, and Samson Zhou. Relative error fair clustering in the weak-strong oracle model. In Forty-second International Conference Machine Learning, 2025a.
11

---

Published as a conference paper at ICLR 2026
Vladimir Braverman, Jon C Ergun, Chen Wang, and Samson Zhou. Learning- augmented hierarchi- cal clustering. In Forty-second International Conference on Machine Learning, 2025b.
Moses Charikar, Sudipto Guha, Éva Tardos, and David B. Shmoys. A constant-facte approximation algorithm for the k-median problem. In Proceedings of the 31st Annual ACM Symposium on Theory of Computing (STOC), pp. 1-10. ACM, 1999.
Vaggos Chatziafratis, Rad Niazadeh, and Moses Charikar. Hierarchical clustering with structural constraints. In International conference on machine learning, pp- 774-783. PMLR, 2018.
Jiaxiang Chen, Qingyuan Yang, Ruomin Huang, and Hu Ding. Coresets for relational data and the applications. Advances in Neural Information Processing Systems, 35:434 2022.
Ke Chen. On coresets for k-median and k-means clustering in metric and euclidean spaces and their applications. volume 39, pp. 923-947, 2009. doi: 10.1 37/070699007.
I Chien, Chao Pan, and Olgica Milenkovic. Query k-means clustering and the double dixie cup problem. In Advances in Neural Information Processing Systems, pp. 6649-6655 2018.
Tuhinangshu Choudhury, Dhruti Shah, and Nikhil Karamchandani. Top-m clustering with a noisy oracle. In 2019 National Conference on Communications (NCC), pp. 1-6. IEEE, 2019.
Eleonora Ciceri, Piero Fraternali, Davide Martinenghi, and Marco Tagliasacchi. Crowdsourcing for top-k query processing over uncertain data. IEEE Transactions on Knowledge and Data Engineering. 28(1):41-53, 2015.
Ryan Curtin, Benjamin Moseley, Hung Ngo. XuanLong Nguyen, Dan Olteanu, and Maximilian Schleich. Rk-means: Fast clustering for relational data. In International Conference on Artificial Intelligence and Statisties, pp. 7742-2752. PMLR, 2020.
Susan Davidson, Sanjeev Khanna, Tova Milo, and Sudeepa Roy. Top-k and clustering with noisy comparisons. ACM Transactions on Database Systems (TODS), 39(4):1-39, 2014.
Yinhao Dong, Pan Peng, and Ali Vakilian. Learning-augmentted streaming algorithms for approxi- mating max-cut. In 16th Innovations in Theoretical Computer Science Conference (ITCS 2025), pp. 44-1, 2025.
Eyal Dushkin and Tova Milo. Top-k sorting under partial order information. In Proceedings of the 2018 International Conference on Management of Data, pp. 1007-1019, 2018
Ehsan Emamjomeh-Zadeh and David Kempe. Adaptive hierarchical clustering using ordinal queries. In Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, pp- 415-429. SIAM, 2018.
Jon C. Ergun, Zhili Feng, Sandeep Silwal, David P. Woodruff, and Samson Zhou. Learning- augmented SkS-means clustering. The Tenth International Conference on Learning Repre- sentations, ICLR, 2022.
Aryan Esmailpour and Stavros Sintos. Improved approximation algorithms for relational clustering. Proceedings of the ACM on Management of Data, 2(5):1-27, 2024.
Chunkai Fu, Brandon G Nguyen, Jung Hoon Seo, Ryan S Zesch, and Samson Zhou. Learning- augmented search data structures. In The Thirteenth International Conference Learning Rep- resentations, 2025.
Sainyam Galhotra, Sandhya Saisubramanian, and Shlomo Zilberstein. Learning to generate fair clusters from demonstrations. In Proceedings of the 2021 AAAI/ACM Conference AI, Ethics, and Society, pp. 491-501, 2021.
Sainyam Galhotra, Rahul Raychaudhury, and Stavros Sintos. k-clustering with comparison and distance oracles. Proceedings of the ACM on Management of Data, 2 2024.
Barbara Geissmann, Stefano Leucci, Chih-Hung Liu, and Paolo Penna. Sorting with recurrent com- parison errors. In 28th International Symposium on Algorithms and Computation (ISAAC 2017), 2017.
12

---

Published as a conference paper at ICLR 2026
Barbara Geissmann, Stefano Leucci, Chin-Hung Liu, and Paolo Penna. Optimal dislocation with persistent errors in subquadratic time. Theory of Computing Systems, 64(3):508- -20, 2020.
Barbara Geissmann, Stefano Leucci, Chih-Hung Liu, and Paolo Penna. An optimal sorting algorithm for persistent random comparison faults. arXiv preprint arXiv:2508. 2025.
Debarghya Ghoshdastidar, Michaël Perrot, and Ulrike von Luxburg. Foundations of comparison- based hierarchical clustering. In Advances in Neural Information Processing Systems, pp. 7454- 7464, 2019.
Kasper Green Larsen, Michael Mitzenmacher, and Charalampos Tsourakakis. Clustering with a faulty oracle. In Proceedings of The Web Conference 2020, WWW '20, pp. 2831-2834, 2020.
Elena Grigorescu, Young-San Lin, Sandeep Silwal, Maoyuan Song, and Samson Zhou. Learning- augmented algorithms for online linear and semidefinite programming. Advances in Neural In- formation Processing Systems, 35:38643-3388 33654,, 2022.
Stephen Guo, Aditya Parameswaran, and Hector Garcia-Moling So who won? dynamic max dis- covery with the crowd. In Proceedings of the 2012 ACM SIGMOD International Conference Management of Data, pp. 385-396, 2012.
Sariel Har-Peled and Soham Mazumdar. On coresets for k-means and k-median clustering. In Proceedings of the thirty-sixth anmual ACM symposium on Theory of computing, pp. 291-300, 2004.
Max Hopkins, Daniel Kane, Shachar Lovett, and Gaurav Mahajan. Noise-tolerant, reliable ac- tive classification with comparison queries. Conference on Learning Theory, pp. 1957-2006. PMLR, 2020.
Chen-Yu Hsu, Piotr Indyk, Dina Katabi, and Ali Vakilian. Learning-based frequency estimation algorithms. In International Conference on Learning Representations, 2019.
Lingxiao Huang, Shaofeng Jiang, and Nisheeth Vishnoi. Coresets for clustering with faimess con- straints. Advances in neural information processing systems, 32, 2019.
Wasim Huleihel, Arya Mazumdar, Muriel Médard, and Soumyabrata Pal. Same-cluster querying for overlapping clusters. In Advances in Neural Information Processing Systems, pp. 10485-10495, 2019.
Christina Ilvento. Metric learning for individual fairness. In 1st Symposium on Foundations of Responsible Computing (FORC 2020), 2020.
Piotr Indyk, Ali Vakilian, and Yang Yuan. Learning- based low-rank approximations. Advances in Neural Information Processing Systems, 32, 2019.
Ehsan Kazemi, Lin Chen, Sanjoy Dasgupta, and Amin Karbasi. Comparison based learning from weak oracles. In International Conference on Artificial Intelligence and Statistics, pp. 1849-1858. PMLR, 2018.
Taewan Kim and Joydeep Ghosh. Relaxed oracles for supessueee clustering. arXiv preprint arXiv:1711.07433 2017a.
Taewan Kim and Joydeep Ghosh. Semi-supervised active clustering with weak oracles. arXiv preprint arXiv: 03202, 2017b.
Rolf Klein, Rainer Penninger, Christian Sohler, and David P Woodruff. Tolerant algorithms. In European Symposium on Algorithms, pp. 736-747. Springer, 2011.
Ngai Meng Kou, Yan Li, Hao Wang, Leong Hou U, and Zhiguo Gong. Crowdsourced top-k queries by confidence-aware pairwise judgments. In Proceedings of the 2017 ACM International Confer- ence on Management of Data, pp. 1415-1430, 2017.
Don R Lick and Arthur T White. k-degenerate graphs. Canadian Journal of Mathematics, 22(5): 1082-1096, 1970.
13

---

Published as a conference paper at ICLR 2026
Tie- Yan Liu et al. Learning to rank for information retrieval. Foundations and Trends@ in Informa- tion Retrieval, 3(3):225-333 -331, 2009.
Stuart Lloyd. Least squares quantization in pem. IEEE Transactions Information Theory, 28(2): 129-137, 1982.
Arya Mazumdar and Barna Saha. Clustering with noisy queries. In Advances in Neural Information Processing Systems, pp. 5788-5799, 2017a.
Arya Mazumdar and Barna Saha. Query complexity of clustering with side information. In Advances in Neural Information Processing Systems, pp. 4682-4693, 2017b.
Ramgopal R. Mettu and C. Greg Plaxton. Optimal time bounds for approximate clustering. In Adnan Darwiche and Nir Friedman (eds.). UA/ '02, Proceedings of the 18th Conference in Uncertainty in Artificial Intelligence, pp. 344-351. Morgan Kaufmann, 2002.
Adam Meyerson, Online facility location. In Proceedings 42nd IEEE Symposium on Foundations of Computer Science, pp. 426 431. IEEE, 2001.
Michael Mitzenmacher and Sergei Vassilvitskii. Algorithms with predictions. Communications of the ACM, 65(7):33-35, 2022.
Benjamin Moseley, Kirk Pruhs, Alireza Samadian, and Yuyan Wang. Relational algorithms for k- means clustering. 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021), pp. 97-1, 2021.
Nikolaos Nakis, Niels Raunkjær Holm, Andreas Lyhne Fiehn, and Morten Mørup. How low can you go? searching for the intrinsic dimensionality of complex networks using metric node em- beddings. International Conference on Learning Representations (ICLR), 2025.
Vassilis Polychromopoulos, Luca De Alfaro, James Davis, Hector Garcia-Moline and Neoklis Poly- zotis. Human- top-k lists. In WebDB, pp. 25-30, 2013.
Rahul Raychaudhury, Wen-Zhi Li, Syamantak Das, Sainyam Galhotra, and Stavros Sintos. Met- ric clustering and graph optimization problems using weak comparison oracles. Proceedings of Machine Learning Research vol, 291:1-54, 2025.
Sam T Roweis and Lawrence Saul. Nonlinear dimensionality reduction by locally linear embed- ding. science, 290(5500):2323-22224 2000.
Sandeep Silwal, Sara Ahmadian, Andrew Nystrom, Andrew McCallum, Deepak Ramachandran, and Mehran Kazemi. Kwikbucks: Correlation clustering with cheap-weak and expensive-strong signals. In Proceedings of The Fourth Workshop on Simple and Efficient Natural Language Pro- cessing (SustaiNLP). pp. 1-31, 2023.
Vaishali Surianarayanan, Neeraj Kumar, and Stavros Sintos. Clustering with set outliers and ap- plications in relational clustering. Proceedings of the ACM on Management of Data, 3(5):1-27, 2025.
Omer Tamuz, Ce Liu, Serge Belongie, Ohad Shamir, and Adam Tauman Kalai. Adaptively learning the crowd kemel. In Proceedings of the 28th International Conference on International Confer- ence on Muchine Learning, pp. 673-680, 2011.
Joshua B Tenenbaum, Vin de Silva, and John C Langford. A global geometric framework for nonlinear dimensionality reduction. science, 290(5500):2319-23333 2000.
Antti Ukkonen. Crowdsourced correlation clustering with relative distance comparisons. In 2017
IEEE International Conference on Data Mining (ICDM), pp. 1117-1122. IEEÉ, 2017.
Petros Venetis, Hector Garcia-Molina. Kerui Huang, and Neoklis Polyzotis. Max algorithms in crowdsourcing environments. In Proceedings of the 21st international conference on World Wide Web, pp. 989,998, 2012.
14

---

Published as a conference paper at ICLR 2026
Victor Verdugo. Skyline computation with noisy comparisons. In Combinatorial Algorithms: 31st
International Workshop, IWOCA 2020, Bordeaux, France, June 8-10, 2020. Proceedings, pp- 289. Springer.
Haike Xu, Sandeep Silwal, and Piotr Indyk. A bi-metric framework for fast similarity search. arXiv preprint (2289), 2024.
I-Cheng Yeh. Default of credit card clients. UCI Machine Learning Repository, 2009.
15

---

Published as a conference paper at ICLR 2026
A LOWER BOUND FOR k-CLUSTERING IN THE R-MODEL.
Theorem A.I. Every ) -approxmattiionnnn algorithm for the k-median/mmans clustering problem in the R-model must contain least 2 centers, where n the number of vertices the input metric space and 3 S k- = (1).
Proof. We show the proof for the k-median clustering, however all results can be extended to k- means clustering. We show stronger result, assuming that the probabilistic noise is 0, i.e., perfect oracle.
We construct a finite metric space Σ (V,d) of n vertices as follows. For simplicity, we assume that n' = 2 is an integer. A set of k - 1 vertices U = Wi..... ug-1 are contained in with d(u, u2) Ç, for every i i [k 11. for parameter < > 0 that we specify later. Furthermore,
there exists a set Y of n' vertices y|4) , Yn such that d(u; (1) 3/ (1) = 0 for every i i [M]- Moreover, there are l - groups of vertices, X₂ = (=]²)
(8) n'-1h w' } such that each group contains n' 1 vertices, while d(x;
n' n' 11. X3 = {x)
...
x== = [
(k)
2 (h)
for every h E f k) and every i j E [n' 1]. Let X =
X,. For every yi E Y (for
i E [n'] and x E X. d(z, v.) = 1. For every æ1 E X, and I2 E Xy. where # j k),
d(x),22) 1. Finally, for every vertex t X UUY and u U. d(t, u) Ç. it easy to verify that the function d(.) satisfies the triangle inequality, so Σ is metric space.
We note that under the R-model (with probabilistic noise 0) an algorithm cannot distinguish between an instance of the metric space where n² and C = 2. Indeed, for both choices, > 1, so the ordering all pairwise distances of the vertices in remain the same for = n and ( =
Next, we show that no set of centers of size at most 2k: 2 returns an o apprroxiioinni solution for both undistinguishable instances of k-median clustering on V with Ç = 2 and (= n²3
First, consider the case where Ç = n². The optimum set for k-median clustering for V is PT
U U [v}. where Y, with OPT! COST (V) (# 1) (k 1).
If Ç 2, then the optimum set for k-median clustering on V is Pr {v) U (Un=a.... mh). where
y E Y, and Iy E X₁, for every h E (2.....k) k} with OPT = COST P3 (V) = 2(k - 1).
For Ç = 2, any apnapopprxxiitnonn solution R C V of size at most 2k 2 must include one (arbitrary) vertex from every group X; (for every (2..... k)) and one (arbitrary) vertex from leading to an approximation ratio 2-1 = 2(n). Without loss of generality assume that a set R contains one arbitrary vertex 2[k-1)
Y. If this is not the case, then the k-median cost will be at least
from Y, one arbitrary vertex for every X,, for every i {2...., k), and h arbitrary vertices from U. Notice that COST) (V) 2. Recall that in the R-model no algorithm can distinguish the two instances with Ç = 2 and ( = n². Hence, if selected as a solution of size 2k 2 for the k-median instance when Ç 2, then R will also be selected as solution for the k-median instance when < = n². However, when Ç = n then OPT ( 1) (k - 1) and COST (V) n² so the approximation ratio is 2(n²). The result follows.
B ALGORITHM FOR GENERAL METRICS
We are given set of vertices V from metric space Σ = (V, d) with M and access to a noisy
quadruplet oracle Ô over Σ with known enror rate < 3. Given cluster size k and parameter p E Σ>1 U (oc), ), the algorithm outputs a set C C V of size O polylog n) and a mapping M V + C. For clarity of exposition, we restrict to the k-median case (p 1) and assume yp is bounded by fixed constant below 1/4. The rest of this section is organized as follows: Section B. presents the main algorithm, while Section B.2 describes a key subroutine.
16

---

Published as a conference paper at ICLR 2026
B.1 ALG-G
Overview. The algorithm proceeds in rounds. Initially, V1 V. In round i, the algorithm processes V, and removes a subset of vertices obtain smaller Vi+1 V₁. The algorithm terminates when VV ( log" n) or the number of rounds exceeds (log n). Throughout, we use D = Ollog n) to denote the maximum dislocation bound of PROBSORT on any set of edges.
Round The algorithm proceeds as follows.
Sampling. Sample uniformly at random (with replacement) a set of vertices 5/", S of sizes mşs1 es1k log" n. and ms2 es2k log n respectively, where 6s1, 02 are suitable constants. Let S: = S US!
2. Ordering edges. Let X, = E s and compute xx, PROBSORT(2.).
3. Kernel and guard sets. Let Mwwnn = 2 max m in log D}, where Cwin is a sufficiently large constant. For each 5 5(", let Xg,s = E(s, s(2)) and Tx.. the ordering of Ix, induced by mx,, For every s("), compute
KERNEL,(S) (w S/²) RAAKK [[s. w|l I mwin
GUARD; {g E S!!2) miinn + 2D < RANK [1s 2m + +DD].
Filtering. For any S E S (11) and v E V,, define the proximity score
PCOUNT,(V)
Σ 1(ā((s,v) {s,g]) returns "d(s, s )
gEGUARD;(S)
where [ccondition] is the indicator function that returns if the condition holds, and 0 other- wise. Compute V {v V; \ S; max SES!") PCOUNT,(V) [mwin/2 /2]]-
Approximate nearest neighbors. Let y4 E(S(1) Vi). Compute :T, ADDSOORT()) using ALG-TESTER (Subsection B.2 as the comparator. For each V/, let fy be its first incident edge Ty,, Set N₂ (f, : v V!).
Safe-set and mapping. Let TN. be the ordering of N; induced by Ty, Define V" {v E V₁ RANK (f,) < [Va/44). For every v E V define M,(v) as the endpoint of f, in s!"). For every S,, define M.(v) := v.
7. Recurse. Set V,+1 = V, (V" U U;) and proceed to next round.
Final output. Let i* denote the last round. The final centers are C:= V₁. -U S,. Let M,- denote the function that maps every vertex in V,- to itself. Finally, define the global mapping M as the union of the per round mappings M = U M, This is function from V + C since each M; is defined on a disjoint round-specific set.
Weighted coreset. We also obtain weighted coreset by assigning each C weight equal to the number of original vertices mapped to it, namely w(u) = l e V M(v) = u The pair (C, w) defines the coreset.
B.2 ALG-TESTER
Whenever the tester is invoked in round i, is given two edges e = (si, vi and e₂
(sz, v2). with S2, E s(1) and V1, E V; \ 5(2) It is also given access to the ker- nel sets KERNEL; (SRNEL and the global ordering TI,- From these, forms = E(s,, (S))EL,(S:)) E(s,, KERNEL; (s))), and computes the ordering of Z induced by mx,
1. Case S # S2.
17

---

Published as a conference paper at ICLR 2026
(a) Kernel Selection. Let e* be the last edge in T2. Determine whether it belongs to (,,, KERNEL,(S)) or (S2,, KERNEL,(S2)). Without loss of generality, assume e" E(5), KERNEL;(S))). RANK (152, w)) E [2mwin D, 2m and call the remainder KERNAI (S2).
Remove every vertex E KERNEL, (5.) such that
(b) Majority Test. Compute
TCOUNT
Σ
1[Q(ss1, v1), (w, says "d(s), v1) > ((W,v2)")
WEKERNEL'
Output "d(si, v1) > v2)"" wise.
S TCOUNT > L KERNEI (s=))), and the opposite other-
2. Case S1 52-
Set KERNEI'((2) (ERNEI,((2)) and the same majority test in Case (a).
B.3 ANALYSIS
We first establish that no quadruplet query is ever repeated between rounds and within certain steps of a round. We refer this as the isolation property. Next, in Section [.3.I we prove certain properties that hold in each round. Finally, in Section B.3.2 we combine the guarantees to establish global correctness.
Lemma B.1 (Isolation). The algorithm satisfies the following properties:
1. No two rounds rely on the outcome of the same quadruplet query.
2. Within any round, there is no overlap between the quadruplet queries used by PROBSORT(X.) with those required compute any proximity score PCOUNT&(.). or those required by any invocation of ALG- TESTER.
Proof. Since V V" \ (s U s(a))) it follows that V, n (S U U.S 0. Therefore, the (2)
sampled sets S(1 S C V, are disjoint from previous samples. This implies that the corresponding KERNEL;(-) S s,²2) and GUARD;(-) C s(2) are disjoint from previous rounds.
X; = ((S))) - 2(2)
Hence, no quadruplet query is ever reused across rounds.
Within a round i, for any E s!"), the computation of PCOUNT, always performed with E V, s Thus, every query triggered by involves edge from {(S) (1) V, ((s)))) Similarly, every query issued by ALG-TESTER includes at least one edge from E(S V. \ (((2). Since
XG ((S V, ) = 0. quadruplet queries used for computing proximity scores or those used by ALG- TESTER cannot overlap with any query used by PROBSORT(Z{), which always compares two edges from X,,.
B.3.1 PER-ROUND GUARANTEES
We first show that in every round the ordering has bounded dislocation, the kernel and guard sets are confined to the top-ranked vertices, and that kernels are always closer than guards
Lemma B.2. In any round with probability at least n -1(1)) the following properties hold simultaneously:
(i) nx, has maximum dislocation D Ol)
(ii) For every s s( and every v (ERNEL,(S) (U)RD, Pos,(v, V,)
[V_
100ms:'
(iii) For every E s!), any W E (S), and any (U)RD, d(s, w) < d(s,
Proof. We first start with the straightforward proof of (i). By Lemma B.1 quadruplet queries are not repeated between rounds. Therefore, applying Lemma 2.1 to X, E(S! s(2)), ), we have that
TX, has maximum dislocation most D with probability least -/3
18

---

Published as a conference paper at ICLR 2026
Then we show (ii). Fix some round i. For any s E s define B(s) = {v V Poss(v. V.) -
100 ms: j. For any fixed s E s(1), since s(2) is drawn uniformly and independently with replace-
[v.
ment, the random variable N₂- == =1 | n B(s) is binomial with mean [B[NG] mss
[Bss
VV
msz Recall that ms2 es2 log n and msi = esi log n. Thus [[N]]
log Observe
100 mss:
that min = 2 (nwix/wwn log n. D (logn).
Assume 6s2 is large enough that [[]]] max 1000m 1000 log n. }. By a standard Chernoff bound, we get
Pr[N; < 50] I Pr[NN ]E[N
exp((-I[NN]/S)) S n
Taking union bound over all s!!) with probability at least n N. 500mwin for every S (())
So far the lower bound on N₂ and (i) hold with probability - n (1(1) We now continue the analysis conditioned on this. Fix some
s( Since any restriction TX., inherits the same
maximum dislocation bound as Tx,,, it also has maximum dislocation D. Thus, for any edge {s, E
C(s, S if's B(s), then RANK ((3,s')) must be at least N, 15--D D 2 500mmwi D. Therefore, for every edge {s, v) E Es, KERNEL, GUARD, it holds that RANK mx [[s, = 2m +
2D < 500m
so v E (s). D. By definition, s!"),, so
Finally, we show (iii). We note that for any w E KERNEL, and g E GUARD; we have
RA {s, w) S min::
RANK TX, {s.g] g) Muiin + 2D.
With maximum dislocation D, the true rank of every kernel edge is most min D while the true rank of every guard edge exceeds mywin + D. Hence, every kernel edge precedes every guard edge in the true order, and therefore d(s, w) d(s. g). Thus, all of (i). (iii) hold.
Next, we show that the proximity score is a reliable indicator: vertices nearer than all kernels yield large scores, while those farther than all guards yield small scores.
Lemma B.3. In any round i, conditioned on Lemma B.2 with probability at least 1 - n n the following hold simultaneously for every s(1)) and every V, \ s5!2)
(i) If d(s, v) & maXWEKSRNIL, d(s, w) then PCOUNT,(V) > |m-iin/ / /2/
(ii) If d(s. v) max d(s. g) then PCOUNT, < [mii// /2wiin/2j..
(iii) PCOUNT), |mwin/2] then POs,(v, V,) S
V... 100ms1
Proof. Fix round and vertex E s! Consider any E V, (s). Recall that
PCOUNT,(V) = Σ 1(ā((s,v), says d(s, v) s d(s,g)).
(S)
mingeGuARD, d(s,g) Moreover, by Lemma B.I quadruplet queries involved in computing PCOUNT, do not overlap with those used by (ROBSORT(X.).
By Lemma B.2 we have maN d(s, w)
If d(s, v) 5 maxxEEERNEL,(s) d(ss, w), then the correct answer to every comparison "Yes", For sufficiently large owin in Mwin max (Cwin log n, D), Chernoff bounds yield Pr Pr(PCouNT,(V) < [mwin/2] 2 < cxp(-0(mwin) < n Similarly, if dis, v) > maxgEGuARD.()) d(s. g). then the correct answer to every comparison is "No" and Pr (PCOUNTTT,()) > [mwin/2]] < n Taking a union bound over all pairs (s, v) with E S and E V₁. both events (i) and (ii) hold with probability least 1 -1
19

---

Published as a conference paper at ICLR 2026
Finally, from (ii), if PCOUNT,(v) | /2] then d(s,v) v) < mOX d(ss, w). From
Lemma B.2 we have that for every vertex w E (ERNEL; it holds that POS,(w, V,) _ Hence, (v, Vi) & mAXWEXERNEL,(S) (w, V:) S MJ
100mg1
100mg
Next, we establish that filtering removes only a small fraction of vertices, while ensuring that all survivors are well-separated from the kernel sets.
Lemma B.4. In any round i, conditioned Lemma B.2 with probability 1 n the following hold simultaneously:
(i) Every E
e V satisfies d(s, v) maX d(s,w) for all s.
(ii)
VII N
V...
Proof. Conditioned on Lemma B.2 the conditions in Lemma B.3 hold with probability at least
n
Case (i) Lemma B.3 implies that for every s E s!") and every v V, S d(s, v) maXWEKERNEL.CG d(ss, w/ then PCOUNT,(V) [mwin/2 22.. By the definition of V;, node V; is excluded from V if ses() PCOUNT, 2 [m/in/2]] So it follows directly that every E V
must satisfy the claimed inequality for all s E S.t)
Case (ii) Lemma B.2 guarantees that for each E 5!1))
(ERNEL GUARD,
{ueV: (u, V₁) S [V1((100ms))
Lemma B.3 (iii) implies that for every s s(1)) and every v E V, S((2) if POSs(v, V,) > (100(100m)))) then PCOUNT,(v) < Lt/wii//].. Hence for every vertex V, s that is not included in V there exists at least one s E s! such that Pvs V;) < Val/(100msz) Thus, any vertex (2)
cause at most (V11(1100ms1) vertices from V, s(2) to not be included in V,- There are mş1 samples in s(1) so at most Vs1/100 vertices will not be included in V Therefore, [V] 2 VV] Vs]/100 2 (3/5)VV,). as claimed.
Lemma B.5. In any round i, conditioned on Lemma B.2 the following holds with probability at
least 1 - 4= for any query q (1sı, v1), (52, v2)) with 51, $2 s²") and v1, E V, s
if
d(s,.vz) WEKERNEL,(S))
max d(sy.w) for = 1.2,
then ALG-TESTER(() behaves like an adversarial quadruplet oracle with error p 1.
Proof. We focus the case * Sz: the other case is simpler. Assume that e* E(Si, KERNEL,(S))) such that RANK (e*) = (2). The tester discards any vertex u from KERNEL, with RANK,, (($2,u)) u}) [|2] D, (2()- Since TT has maximum dislocation D. every KERNEL/((>) satisfies
d(s2,w) < d(e") < d(si.vi).
Moreover, assuming the constant Cwin is large enough in mwin |EERNEL((Z2] = 2m - D = 2(log n). since = Ologgn).
2 max log n, D), it holds
Each oracle query is correct independently with probability at least 1 4 3/4. Let |KERNEL((>>)] The tester outputs "yes" if more than T == [m/2] comparisons say {s), vi is larger, and "no" otherwise.
20

---

Published as a conference paper at ICLR 2026
Case 1: TCOUNT (tester outputs "yes"). This only be wrong if d((2,, s2) 2d((1, S1). In that case, for every w E (E2)
d(v2, w) d(v2, s2) d(s2, w) 2 d(v2, - d(c²) 2d(v1, 51) - d(c*) > Si).
Thus every "yes" response is incorrect, and by Chernoff bounds Pr[T > r] n-
Case 2: TCOUNT I T (tester outputs "no"). This can only be wrong if ddvi, > (2) In that case, for every w E (52)
d(v2,w) w) d(v2, + d(s2, w) 2d(v2, < d(),,
so every "no" response is incorrect. Again, Pr(T S
The case 5 S2 is analogous: in Case we have directly d(s2, w) S d(s2, v1), and in Case 2 we have d(s2, w) 2 d(v2, $2). Thus, in all cases, the tester fails with probability at most n
Finally, union bounding over (n²)) possible queries in round gives overall failure probability at most as claimed.
Lemma B.6. In any round i of ALG-G, conditioned on Lemma B.2 with probability at least 1 1- -n- the following holds:
(i) for v VG d(v, S 5,(
(ii) VII 2 /1144
Proof. Conditioned on Lemma B.2 each of Lemma B.3 Lemma B.4 and Lemma B.5 fails with probability at most n n4, By a union bound, all of them hold simultaneously with probability 3n We analyze under this assumption.
By Lemma B.4 for every V and every s s(1)) we have d(s, v) > maxWEKERNEL, d(ss, w).
pairs of edges in y, E(S!") Vi), every invo- cation of ALG-TESTER satisfies the preconditions of Lemma B.5 Specifically, for any query s!") and V1, E V,, the following condition holds for d(vy,s;)
Since ADVSORT only calls ALG-TESTER
q ((s1, v1), v2)) with $2
j = 1,2: 2:
d(s,,w).
max WEKERNEL
Therefore, by Lemma B.5 whenever ALG-TESTER is invoked in behaves like adversarial quadru- plet oracle with error = 1. It follows from Lemma 2.2 that the ordering Ty, is 4-sorted: for any e1, e2 E 4r.
RANK (01) < RANK (62) = d(er) S 4 d((2)).
Let f. be the first edge incident to V in my, and recall M,(v) its endpoint in s(1) Then for any s!".
d(v. = d(f.) s .d([s,v)).
hence d(v, M((v) < d(v, s This proves (i).
For (ii), Lemma B.4 guarantees V1] 2 & Vr]. The safe set is
V (v E V RANK (f.) S V.1/4].
Since [V] 2 3/V. at least /v1/4 vertices of V satisfy the rank condition, and hence [V] [Va]/4, This proves (ii).
Structural Property. Let OPT be the optimal k-median cost, and let C* denote the set of centers in an optimal solution. Let = OPT) (V)/n. For a round i, define a vertex v E V; as good
S(v.S.1 < max(C, 2 d(v, C*)}, and bad otherwise. Let VØ, Vy be the good/bad sets so V; V U Vg.
21

---

Published as a conference paper at ICLR 2026
Lemma B.7. In any round i, with probability least 1 -
|V9|
0
Vill logn
Proof. Let c E C*. Furthermore, let Ne S the set of all vertices that get mapped to c according to the optimal clustering. Fix round i, and let s s! be the vertex such that arg min seg( d(c,s).
Define
B = NV; POS:(v, V.) < Posc(s", V.)}.
Observe that if E (Ne V,) B, then d(v, c) 2 d(s", c) and by triangle inequality d(v, s*) S 2d(v, c). Hence, every v V, 2 is good. Therefore, V nNe S 2 and [Nen V I POS. Vt).
For any constant $ es1.
(5
Pr V
nX
Vil kr log
Pr S;
(s" 2
V
(1
ky log n
Jry log
n 7(1)
Union bounding over E C* gives
Vdl
S
B.3.2 PUTTING EVERYTHING TOGETHER
Define the event IDEAL as all the conditions in all preceding lemmas hold. We perform subsequent analysis under this assumption. We prove structural lemmas: in each round, there are sufficiently many surviving good vertices to control the cost of the removed bad ones (Lemma B.9 and across
all rounds we can construct an injection from bad to good vertices (Lemma B. 10). We use these
structural guarantees to bound the total cost by O(1) ( (Corollary B.11).
Lemma B.8. With probability at least 1 - - -1(1,, the event IDEAL holds; i.e., all properties from B.7 holds simultaneously across all O(log n) rounds.
Lemmas B.2 B.3
B.4
4
B.5
B.
Let R, V U s U s!? be the set of vertices removed in round Define V V n V to be the subset of bad vertices that actually get included in the safe-set in round and let Vo := U V denote the collection of all such vertices across all rounds. We mainly need to worry about these. Similarly, define V V R₂ the set of good vertices that not included in the safe-set in round i, and let V == U._ Vi be the union of all such good vertices.
Lemma B.9. Conditioned on the event IDEAL, the following hold for every round i:
1. V 2 V.1/100.
2. For any V and g E Vg, d(b, & 4 4dgg Ct).
Proof. By Lemma B.4
VI 2 V.l. Since the safe-set removes exactly |M//4 vertices, it follows
that
M V/I 2 M H
I Vil-
By Lemma B.7 at most O([Va// log n) of these are bad, and since R, = V U s!!!! U s!! by ensuring ni 52 (mm1)) Q(m52) and, we can ensure that
7 V.
7
V
V
R.l = 1(V R2) V 2 V
0
2 /V|/100.
20
log
always holds for suitably large n.
22

---

Published as a conference paper at ICLR 2026
Next, recall that V consists of vertices that appear among the the [|V1/44] edges in nx,, Since AN, 4-sorted (Lemma 2.2). for any u E V" and any w E V; V we have
d(fu)) S d((w))
By construction of M,, this yields
d(u, M,(u) I 4 4d(ww C*)
for any u E V/ w V, V.
Since V CV V. and V V,, this implies that for any g E V and b V M((b)) < 4dgg, C*).
Note that in the case of the last round V 1 and the claim vacuously holds.
Lemma B.10. Conditioned on the event IDEAL, there exists map Ap V + V such that:
(i) for every E VG the image satisfies (bb) E V (i.e. each removed bad vertex is mapped a surviving good vertex from the same round),
(ii) da is an injection.
B.7 in every round i, IV n V (V: R.) n VI and of size [V]]
Proof. By Lemma
100 log while by Lemma B.9 V
V.l
C
2
VJ] 100
Moreover, since each round removes exactly fraction
of V,, we have
3 Vil-
Meal s
We construct & by reverse induction over the rounds. For the final round = r, the claim holds by default there are no bad vertices, i.e. V 0.
Assume injections bhy are defined for all j > such that the injection property is preserved so far. Let
U VVV
j=i+1
denote the of used vertices. Therefore,
|
V
M
Σ (3/4)*
3
100 logn
100 log
100 log
j=++1
Now define Vrem
V \ U. Then
V+
3/V.
V
V.1.
M > V
100
100 log
150
100 log n
for sufficiently large n. Thus an injection This completes the proof.
V Viaw exists, and its image is disjoint from U.
Corollary B.11. Conditioned on the event IDEAL, Evey d(v) 0(1) (PT.
Proof. By Lemma B.10 and Lemma B.9 there exists an injection V V9 such that d(b, ((b)) < d V (b). C*).
Summing over V and using that injective.
Σ d(b. < 4 Σ d(V((b)CC) S 4 Σ d(v.C) 4VPT.
beVb
23

---

Published as a conference paper at ICLR 2026
Note that by the definition of "good", for every V V must have been good, i.e. d(v,M(v)) & max|C, 4d(v, C = (V)
Hence
max(C, Cdlg. Ct) x (V) OPT (VPT
Σ ((v)) s
Σ
gEViVe
vEViV'
Taken together,
dd(v,M(v) = -
VEV
Query Complexity. Since PROBSORT(.) is always invoked on a set of size msi ms2 Okk" polyloly n), each call uses Ok** queries. Computing proximity scores requires one evaluation per (s, v) pair, i.e. 0115,1) Mil) O(kkpolylog n) queries in round. Each invocation of ALG-TESTER occurs within ADVSORT on yr = E(S, Vý), contributing an- other OAkkpolylog n) queries. Therefore, the total per-round query complexity is O(Ink + ke po))olyyog n)) = Onn polylog Since there are r = Ollog n.) rounds, the overall query com- plexity is Onk polylog
Notice that all results, in this section, up constant factors in asymptotic analysis, can be extended to any (k:, -)clusteri instance, where p is a constant or oc. We conclude with Theorem 3.1
C BOUNDED DOUBLING DIMENSION
In this section, we show how to improve the query complexity of ALG-G to O(In + k2) polylog n) when the underlying metric has bounded doubling dimension. We use the following data structure and query procedure from Raychaudhury et al. (2025).
Lemma C.1. Let Σ = (V, d) be a metric of bounded doubling dimension with M n, and E(V) VV accessible under the R-model. For S C V and a-sorted ordering Te(s) there exists procedure CONSTRUCT(S, TE(S)) that builds structure T without executing any quadruplet oracle, such that given any E V V.S, S, procedure TRAVERSE(T v) returns set F C (v.S)) of size Oppoyylo n) such that minee id(e) S 4a d(v. S). The traversal requires answers (polylog n) quadruplet queries of the form (2), {s3, with s S from adversarial quadruplet oracle with noise μ S 1.
C.I ALG-D
Similar to the general metric case, the algorithm proceeds rounds. We describe the steps of generic round i. The first three steps are identical to ALG-G, but we restate them for convenience.
1. Sampling. Sample uniformly random set of vertices s s C V, of sizes ms1 csik log" n and ms2 es2k log" respectively, where cs1, 652 are suitable constants. Let S. : 5(2) u.
Order edges. Let X; = 8(S!)) ((2)) and compute मx; PROBSORT(())).
Kernel and guard sets. Let m-iin max max log n, D). For each s E s(1), let X;,, E(s, s(2) and xX., the ordering of XG,s induced by Nx.- For every s("), compute
RRANK** ... [[s, wH] S mwin KERNEL;(S) E S!!2) S
GU)RD,($) {g S!??) m.wnn + D < RANK x., (s,g)] 2m D).
24

---

Published as a conference paper at ICLR 2026
4. Identify close pairs. For each + s' S.") compute PCOUNT,(S'. Define (s, close if max max(PCOUNT,(s)) PCOUNT;:(S)) 2 []
5. Partition into classes. Construct graph G; S(1) whose edges all close pairs defined above. As we show in the analysis, the graph G; is Ollog deggenerae,,, i.e., in any subgraph of G3 there exists at least one vertex with degree Ol) We run the greedy coloring algorithm for degenerate graphs Lick & White (1970) on G; to get coloring of the vertices in G, and let
Xi be the number of different colors. We partition s into classes S(1.1) ,...,,; S...,,!!.xi based on their colors. Let e {(u,v) v S!" for each j 1,..., Xi.
Approximate nearest neighbors. For each class s!!.)):
(a) Build. Compute T = ADVSORT(E,)) with ALG-TESTER as the comparator, then con- struct J(6) CONSTRUCT(SŞ"") (T(O)).
(b) Traverse. For each E V, S; run TRAVERSE(T!") .v. During execution, the proce- dure issues comparisons of the form (251,52), (ss, v)) with $1, S2, s(1.)) For each comparison, first check whether
max ( (CCOUNTs, (v), PCOUNT (v), PCOUNTss (v)) 2 [twinn/].
If the condition holds, climinate v and proceed to the next vertex. Otherwise, call ALG-TESTER((SI, $2 {sa, v}) and pass its response to TRAVERSE, If v is not eliminated, TRAVERSE outputs (pooyylg n)) edges from 8(v, s(t.))
edges returned for class j in the previous step, and define y, = - / For every eliminated vertex remove all incident edges from y;, and denote the remaining set by y, Let V == V(y.) \ S,
Collect results. Let y be the
8. Final ordering. Compute my, ADVSORT(Y.) using ALG-TESTER as the comparator. For each E V,, let f, be the first edge incident to Ty.
9. Safe-set and mapping. Let TN, be the ordering of N; induced by Ty,, Define V = {vv E V RANKTN, TN, (f.) S [V:]/4). For every v E V/, define Mi(v) as the endpoint f, s!") For every v É St, define M,(v) ==v.
10. Recurse. Set V,+1 = V, \ (V" U,) and proceed to next round.
C.2 ANALYSIS
Lemma C.2. In any round i, conditioned Lemmn B.2 with probability 1 - n X: O(log
Proof. Fix a round i. By Lemma B.3 we can argue that w.h.p. for every (s E E(S(2)), (s, close then POs,(s', V.) s Vil (100ms:) POSS (s, Vz) [V]/(100mms).
For any s E (S define deg+ == (s' E S.x)) \ (s) pos, V,) s MM//110mss)]] We note that deg" + (s) is not the degree of s in G..
Recall msi = os1 1e log" n. For a uniformly random s' E V, \ (s).
|Val < 100ms1
Pr (s:
100ms1
Over the mi (with-replaacement) draws in s!") \ {s), E(dog (s)] < 100
1 By the Chernoff
bound, for any constant > 10 and large enough n. Pr deg (s) 2 C' Coogg < n 3, By union
bound for every E s.")) with probability at least _ it holds that deg (s) O n).
From the above argument, we can conclude that for every s E s(1) can contribute to at most O(log n) edges being close. Thus, with high probability, for any subgraph Hff G, the total number
25

---

Published as a conference paper at ICLR 2026
of edges is bounded by ()lo [V(H). vertex with degree at most (log n),, and the graph G; is O(log degeenerett Lick White 1970). It is known that the greedy coloring according to the degeneracy ordering can color graph G; with Xi = O(logn) n) colors Lick & White 1970).
Thus, for every subgraph H of G; there is at least some
Lemma C.3. In any round i, conditioned on Lemmna B.2 with probability 1 - whenever ALG-TESTER invoked, it behaves like an adversarial quadrupler oracle with error μ 1.
Proof. Conditioned on Lemma B.2] each of Lemma B.3 and Lemma B.5 holds with probability - n -4. By a union bound, they simultaneously hold with probability n n3 We perform the analysis under this assumption.
By Lemma B.5, ALG-TESTER behaves like an adversarial oracle with error μ if for any query (fs,, v1 1, ($2, vaH). where s/ $/2 E s.'h) and v', V/2 E V2 \ s((), it holds that
d(v),,/) > max d(s),, w) = 1,2).
WEKERNEL
By Lemma B.3 if v(s,v) I max d(ss, w) then PCOUNT,(V) [mwin/2].
Construction phase. Every call compares (2h. {sa. 51} with 5e E 5(1J), Since each s(1,)) is an independent of G; we have that s is not close $2 and S3 is not close $4. Consider the pair (2 Since it is not close, we have max PCOUNTs, ($2), PCOUNT,, ($1)} < |mwin/21
Without loss of generality, assume that PCOUNTs, (52) < win/// /2). From Lemma B.3 have that d(s1, $2 > maX d(s1, w). Similarly, the same inequality holds for the pair {53, Sa), and hence is satisfied.
Traverse phuse. Queries are of the form ((s1;52); {sa, v}) with sr E S(lai) and E V, S, Before invoking ALG-TESTER, the algorithm ensures PCOUNT (v) < | /2], which implies d(v. 5a) (aX d(s3, w). Combined with the argument for [21, above, the tester precondition holds.
Final sorting. Queries are of the form (1 v2H) with 52 E s(1i)) and V1, E V Since any such (s. v} must have passed the traverse step, we have PCOUNT,(V) s [mwin/ /2], and therefore (2) holds.
Lemma C.4. In any round i of ALG-D, conditioned on Lemma B.2 with probability least 1-n2" the following holds:
(i) For every v E VY. d(v, < 5.
(ii) VII N M1144
Proof. Conditioned Lemma B. each of Lemma B.3 Lemma B.4 and Lemma C.3 holds with probability - n By a union bound, they simultaneously hold with probability perform the analysis under this assumption.
n -3 We
By Lemma C.3 all calls to ALG-TESTER are correct. Hence, by Lemma C.I both the construction steps succeed and every traverse step (for non-eliminated vertices) is successful for every vertex in 5(") From Lemmas
and 2.2 the ordering Zz(²) is 4-sorted, for every = 1,..., Xi- From
Lemma C.1 for every vertex V, S,, the set 'j contains edge Cv, E E(v ((.1)) for each class S (1.)) such that d(c,,)) I 16d(v, s( Similarly, from Lemmas C.3 and 2.2 the ordering Ty.
4-sorted.
Let fl be the lowest rank edge incident to E V in ty., and recall Mi(v) is its endpoint in s( Then for every V". d(v, M(v)) = d(f.) < min d(e.,) S 64 64v e.
26

---

Published as a conference paper at ICLR 2026
For part(ii), observe that any vertex eliminated at any stage must have satisfied PCOUNT, > [/iin/ /2] for some s, which by Lemma B.3 implies POS, (v. V,) I MM/(1100mss) Hence ev- ery climinated vertex lies within the lowest-ranked (v10(1)0mgs) for some so in total at most |Vi/110 vertices can be eliminated. Thus, Vil 2 (3/5)/Vil, which immediately implies that M |V 4.
Using the results of Lemmas C.3 we conclude that Evev d(v, M(v)) ((10((1)P))))))) O (V), with high probability.
C.4 along with the analysis in Section B.3.2 for general metrics,
Query Complexity. In step of the algorithm, PROBSORT(X.)) uses ((max(A2 n polylog n) quadruplet queries since [X;]] O(k"polylog n). For every E S |KERNEL,())], GUARD(s) Oppolylog n). Hence, step 4 the algorithm calls O1'"polylogn) queries to the quadru- plet oracle to compute PCOUNT,(s') for every pair + s' E s!!)) S."). In step 6(a), Ej=t...x use polyloly n) queries to the quadruplet oracle over all classes s!1.1) In step 6(b), for each E S, the (TAV v) (including the computations of PCOUNT,, (v)) use O(polylog n) queries, so in total step 6(b) executes O(npolylog n) queries to the quadruplet oracle. In step 8, / = (mpolylog v)), so the procedure ADVSORT(Y. using ALG--TESTER as the comparator, runs (mpolyyog n) queries to the quadruplet oracle. All other steps of the algorithm do not execute any quadruplet oracle query. Overall, our algorithm calls the quadruplet oracle O(nn + k²)polylog n) times. We conclude with Theorem 3.2
| = O(k2polylog n)) so ADVSORT(E))) with ALG-TESTER as the comparator
D IMPROVING THE APPROXIMATION QUALITY
We now present a technique for improving the approximation ratio when the underlying metric E has bounded doubling dimension, Ç O(1), while still ensuring that the number of centers used is @k polylog n.). In fact, our new procedure also constructs a (k; (k,e)-coreset. We assume that e E (0, 1) is an arbitrarily small constant.
D.1 ALG-DI
Context. Suppose have ALG-D(V) and obtained (C, Let F be the total number of rounds in ALG-D(V) and set S(2) = - s(1) and V' = \ C. By construction, M(() E S(1) for every V" and MM(v) for every E C.
Algorithm. The algorithm proceeds follows:
1. Initialization. Set Z 0.
2. Per-center processing. For each s E S(1)
(a) Assigned set. Define
Ug == {v V M(V) = =s.
If was chosen in round of ALG-D(V), then every E U, satisfies (s. E N;. Let mu the order on Ug induced by NN,-
(b) Level sets. For t = 0, 1, 2, ...., [log |U|] define
U {v U, RANK (v) 2 |U.1/2'..
Let
4 minf 12 U
CIMP log n }
where CIMP is a sufficiently large constant that depends on E and Ç. (c) Sampling. For every t < Is, sample with replacement a subset W C Ug of size [W]] CIMP log n. Set
W; = (U w:) u U t=0
27

---

Published as a conference paper at ICLR 2026
(d) Edge sets. For every < tg. compute
Z = E Ws, W,),
and update
- U 2..
3. Augment centers. Let W = Useso) W,. Set C+ = U C. For every E Ct2 set M+ =
4. Ordering. Compute иz. PROBSORT(2).
5. Final mapping. For each V':
(a) Let == MMv)) (the old mapping). Define &, := E(v, Ws). Let me, be the ordering of E, induced by Tz.
(b) Let {v, w"} be the first edge of Te,; note that w' Ws. Set M (v) == w".
D.2 ANALYSIS OF ALG-DI
First, it is straightforward that ALG-DI satisfies the isolation property, i.e., no quadruplet query is ever repeated between ALG-D ALG-DI. We note that all quadruplet oracles executed in ALG-D involved at least one vertex from C. However, in ALG-DI, after the execution of ALG--, the set removed from V", no quadruplet query will be repeated.
Query Complexity. From the analysis of ALG-D, we showed that we executed O((n + poopoly n) queries the quadruplet oracle. Then, in step (4) of ALG-DI we execute PROBSORT(2)) The set Z. contains (kpolyyo n) edges, so we execute O(ppolylog n) additional queries to the quadruplet oracle. Overall, ALG-DI executes O(nn k22 poolooy n) queries to the quadruplet oracle.
D.2.1 FOCUSING ON A FIXED VERTEX
In the following, we focus on fixed E ((L), Let [0,] = Suppose Eneu, d(s,u) mL for suitable L 2 0. This also implies that maxueu, d(s, u) < m C.
that mu, 4-sorted. Based on the order TU, define contiguous partition of Ug into buckets {B, T== where b is defined next, follows. Let T000ape' where Capp is the approximation ratio of ALG-D. For = 0, 2,.,... let B, be the
Fixed buckets. We know from the analysis in Section
next consecutive block in the order ending at the rightmost element whose distance from is at most 2C8
Bo {initial consecutive block up to the last with d(s, u) 8C),
Bi (next block up the last with d(ss, u) s 25L), Since every E U, satisfies d(s, mLC the number of buckets is
b o
01108 log
mL Ollog ) Olog
n ") Ologn).
8C
For the sake of analysis, consider the following recursive partitioning of {B.bk_. (note that we exclude Bo):
Partitioning.
Let i0 = 0. For rounds 1,2,... do:
1. Compute m, Ei [B.] If m, CMP log n, then stop, else proceed.
2. Define the heavy threshold at round r by Tr = You log
m.
3. Let i, be the largest index t {ir-1 1, 1,...,b) } such that the bucket B, contains least Tr vertices.
4. Remove the entire prefix of fixed buckets {B, Vr VE
We now prove certain properties of the above partitioning. Let r- be the index of the last round.
28

---

Published as a conference paper at ICLR 2026
Lemma D.1. In every round r, m, 2 CIPP log" n, there exists index i, E fir-1 1,....b) Whe
such that [i,l 2 Tr 100 log
Furthermore, my+1 I mh and r* I log n.
100
Proof. Let b, == 1 be the number of active buckets in round r. every active bucket was strictly smaller than 100 lo then
my 100 log n2
Mr my
my
B&l br
S log n
100 log
100
Im
which contradiction. Hence, a heavy bucket exists; let ip be the largest index with [B,,| my 100 logn" The above argument also implies that all buckets to the right of 4, can have a total of at which directly implies that r s log
mt vertices. Thus, my+1 most 100
100
For any round r < r", mark an active bucket round as light if its cardinality less than óm, log" n). Let LIGHT, == {t {ir-1 +h... ,,..,, B.ll < 8m, log" n) be the index set of light buckets in round r.
Lemma D.2. For any round r, ELELIGHT, EVEB, d(s,v) s 8 EveB, d(s.v)
Proof. Since it, is 4-sorted and the buckets {B,} are contiguous in the order, for any LIGHT,, for every v E Br, and any V E Bi,, v's,v') S 4 v).
Let V arg min d(v,s). Therefore.
bōm,
dm, 250 log
Σ d(s.u) S
E LELIGHT,
(B.l) 4d(v,s) S d(v,s).
250 log S d(v.s)
BELIGHT, uEB,
Furthermore, d(v.s).
Σ
d(s.v) the result follows.
loo n
vEB
Lemma D.3. With probability at least 1 - n- for every non-light bucket B (i.e., [B] > Jm,/ (1000 log² n) in some round r, ALGGDD uniformly samples at least SIZE. log vertices from B, where 7 is a suitable constant.
Proof. Consider non-light bucket B in some round r. Thus, has least 8 8m 1000 log vertices.
Consider the level sets used by ALG-D with respect to
U U, RANKT,, 2 JU.1/2"}.
Choose to maxft: t: B C }. By maximality of i and the contiguous nature of the buckets, |U < 2m,. For level to the ALG-DI samples uniformly (with replacement) set Wis of size 4MP log n uniformly from U Let X be the number of sampled vertices that fall in B. Then
5m
E[X] = CIP log n
B
2 9MP log n
1000 log
6CMP
log n.
2m,
2000
By a Chernoff bound, for sufficiently large CIMP, Pr[X- SIZE = 7 log n|
S n 12 - Taking
union bound over all Olog² n) possible non-light buckets across r" O(log n) rounds proves the claim.
Lemma D.4. Conditioned on the correctness of (ROBSSOR(22) (so that all induced orders used be- low have maximun dislocation D), there is choice of absolute constants such that, with probability at least n. 88 for every non-light bucket in any round r,
dd(v,M* (v)) S 8 Σ d(s. v). VEB
29

---

Published as a conference paper at ICLR 2026
Proof. Fix non-light bucket B in some round By the bucket construction and the 4-sorted property iu,,, there exists a scale a > such that
S d(s.v) I 4a for every v E B.
Since the doubling dimension is S, it is known that B can be covered by set of m @ balls of diameter at most (6a)/10 whose centers lie B. Consider a collection of such balls and partition B in mn componenis, breaking ties arbitrarily if two points lie in the same ball. Call component light it contains fewer than B /m² vertices, and heavy otherwise. Then the union of light components contains most (1/m) [B] vertices.
Contribution of heavy components. Fix a heavy component B' C B. By Lemma D.3 (applied to the present round and bucket B), ALG-DI draws least SIZE 7 log n. independent uniform samples from B (with replacement), where >> is a sufficiently large absolute constant. Let X be the number of samples that land in B'. Since it contains least [B/m vertices,
SIZE m
log
E[X]
m2
Assume 7 is large enough (it depends on e, that B[X] 100 max (log n, D}. Then by Chernoff bound, Pr[X I D] n n-12 By union bound over all (at most m) heavy components, with probability at least
each heavy component contains least DD samples.
Now fix v inside B' Recall that W, S Ug denotes the collection of all vertices including samples ALG-DI computes while processing Note that W; C+. Since all vertices in B' are within distance 6a/10, for every vertex w E Wg n B' we have
da
() S 10"
By the above arguments, [W, n B| > D.
Since the correctness of PROBSORT(2) implies that the induced order иæ, (the restriction of Tz to (v. W)) has maximum dislocation D. the first edge {v, wn] in Te,, where w* E W 2 W, must satisfy
da
d(v,w") M+ S
10
Summing over all vertices in all heavy components of B contributes at most (5/10) a [B].
Contribution of light components. The union of light contains at most (1/m) [B] vertices. For any v in a light component and any sampled w E W, n B, the triangle inequality and the bucket scale imply
d(v,w) w) < d(v,s) + d(s,w) < 4a + 4o = 8a.
Since Lemma D33 guarantees |W n B 2 SIZE = log 2 DD the first edge in πæ, has length at most Sa. Theretore, vertices in light components within B contribute at most (1/m) -B]- 8a.
Putting everything together. Adding contributions of light and heavy components of B, we get that
5 + m
Σ d(v.M+(v) S VEB
B|a..
10
Since 8 < 1,5 2 1 and f ()) we have that <
8 and the result follows. The probability
mo.
bound 1 n follows from a union bound over all O n) non-light buckets of
Lemma D.5. Fix E S(1), Conditioned on the correctness of (ROBSORT(2)), with probability at least 1 n
Σ ddv, S
Σ d(s.v).
Capp
VEU.
vEU,
Proof. We argue for a single round r and then sum over rounds. Let i, be the index of the rightmost heavy bucket in that round. Henceforth assume Lemma Dn2 Lemma D.4 holds.
30

---

Published as a conference paper at ICLR 2026
By Lemma D.2
Σ d(s,v) S
8. 8. E d(s.v).
LELIGHT, vEB,
vEB:,
By Lemma D.4 gives, w.h.p., p., for each non-light bucket in every round,
dd (v) S 8. Σ v(s.
VEB
VEB
Adding light and non-light contributions within round r,
Σ dlv, (v) s 28
Σ d(s.v).
1 +1 v
vE
Since the buckets are disjoint across rounds, summing the above inequality over all rounds, yields
Σ d(v.M+(v)) S 28
Σ d(s,v) S 20
Σ
v).
VEU,YBO
vEU,)Bo
vEU,
By design for the bucket Bo, E d(v,.+(v)) E d(v,s) S 8 Σ
d(v,s). Combining the
ve Bg
ve
vEU,
above, get that,
E ddv.MM(v)) 35
Σ d(s.v)
VEU,
vEU.
Since 8
the stated bound holds.
T00
Capp
D.2.2 PUTTING EVERYTHING TOGETHER
Corollary D.6. Conditioned on the correctness of PROBSORT(2),, with probability at least n- the refined mapping M+ satisfies
Σ [d(v,M+(v) < . (VT.
VEV
Proof. Fix the event under which Lemma D.5 holds for every E S(), Since each instance holds with probability at least n and (())
n, a union bound gives overall success probability at least 1 - n -7 Summing Lemma D.5 over all s E S(1) yields
Σ d(v. d(v cEVIC
Σ Σ d(v, <
Σ d(s,v) &. Σ d(v,
Capp SES(1) veU,
Capp veVic
vEU,
We also know that
(v))) = E [d(v,M(v) =
Since M is Capp approximaiinnonnn mapping (from ALG-D), we have
d((v,M(v)) I Capp OPT.(V).
Putting everything together gives
Id(v.M+(v)) < E. Ed(,.M(()) S <.PPT
Capp veV
vEV
as claimed.
We conclude with Theorem 33
31

---

Published as a conference paper at ICLR 2026
E ADDITIONAL RELATED WORK
Clustering is a classical problem that has been studied for decades Lloyd
) Charikar et al. Har-Peled & Mazumdar (2004); Chen 2009). For k-median and k-means, Charikar et al.
1999
1999) presented the first constant-factor polynomial-imme approximation, and subsequent work
Mettu Plaxton (002) improved the results. The notion of coresets (compact summaries for scal- able clustering) for k-median and k-means clustering was introduced in HHar-Peled & Mazumdar (2004) and later advanced by Chen (2009). More recently, results of Braverman al. (2021 2022) have improved the sizes of the obtained coresets for clustering.
In another line of work, Xu et al. (024)) studied a weak-strong model in doubling metrics where the weak oracle returns values within a multiplicative factor C > 1 of the true distance, while the strong oracle provides exact distances, Their focus, however, was on building data structures for approximate nearest neighbor search. Finally, (Silwal et al. (2023) examined correlation clustering within a weak-strong framework, but their techniques and oracle definitions do not extend to the k A-cemter/meddian/means setting.
Much of the oracle-based clustering literature has focused on (faulty or exact) cluster queries Mazumdar & Saha (2017a); Huleihel et al. (2019); Mazumdar & Saha (2077b); Choudhury iet al.] (2019): /reen Larsen et al. (2020): Galhotra et al. (2021). which directly identify ground-
truth clusters. For k-means Ashtiani et al. (2016); Chien et al. (2018); (imm & Ghosh (2017a b);
Bianchi & Pennal (2021). and k-median Ailon et al. 2018). such queries, often combined with dis- tance information, have led to stronger approximation guarantees. This is also is closely related
to
algorithms Fu et al. (2025): : Dong et al. (2025); Braverman et al. 2025b
2024
Grigorescu et al. (2022): EEgun al. (2022): Mitzenmacher & Vassilvitskii (2022) Indyk
et al.
2019); Hsu et al. (2019).
Beyond clustering, distance-based comparison oracles have been applied to wide range of problems. Examples include learning fairness metrics [Ilvento (2020). hierarchical cluster-
ing Emamjomeh-Zadeh
Kempel (2018); Chatziafratis et al. (2018); Ghoshdastidar et al. (019))
correlation clustering [kkonen] (2017). 17), classification Tamuz et al. (2011); Hopkins et al. 2020
and knowledge and data engineering Beretta et al. (2023). They have also been leveraged in tasks such finding the maximum element Guo et al. (2012); Venetis et al. (2012). top-k selection Klein cct al. (201T); Polychronopoulos et al. [Ccerr
Ciceri et al. (2015); Davidson
Davidsoo et al. (2014);
(0014)]Kox> Kou et al.
(2017) :: Dushkin & Milo (2018), information retrieval Kazemi al. (2018), and skyline computa-
tion Verdugo
Finally, in relational clustering, the objective is to cluster the output of a join (or conjunctive) query- Since the number of join results can be extremely large, materializing them explicitly often leads to prohibitively slow algorithms. To address this, recent works Agarwal al. (2024); [Esmailpour & Sintos 2024 Chen et al. (2022): Moseley et al. (202I); Curtin et al. pp Surianarayanan et al. (2025) introduce relational oracles that provide summary statistics of the join output together with access to selected key tuples, enabling clustering to be performed more efficiently. This framework, however, differs from the R-model, where the main challenge lies evaluating distances between items through noisy comparisons. In relational clustering, by contrast, the difficulty arises primar- ily from the combinatorial explosion of join results rather than from the complexity of distance evaluation.
USE OF LARGE LANGUAGE MODELS
Large Language Models (LLMs) were used as general-purpose assist tools. Specifically, we drafted all text ourselves, and in several places (mainly in the introduction) we provided our own writ- ten paragraphs to ChatGPT-5 Plus with the instruction to "polish the text." In addition, CharGPT-5 Plus in a limited way to help translate some of our pseudocode into Python code for ba- sic prototyping. No part of the research process, including problem formulation, algorithm design, theoretical development, or experimental analysis, relied on LLMs. All ideas, results, and scientific contributions are entirely our own.
used
32


Reviews:
[{"review_id": "OdaiZVRLzQ", "reviewer": "Reviewer_8Vye", "summary": "The paper studies metric $k$-clustering when instead of distances an oracle is provided that given 2 pairs of points $(a,b)$ and $(c,d)$ returns if $a$ is closer to $b$ or $c$ is closer to $d$. Previous works has establish that with only access to oracle and no distance information, no constant approximation algorithm exists with $k$ centers. This work instead considers constructing coresets, and give and algorithm that outputs a $O(1)$ error coreset with $O(k\\text{poly}\\log{n})$ points and $O(nk\\text{poly}\\log{n})$ oracle queries. If the underlying metric has bounded doubling dimension, the query complexity improves to $O((n+k^2)\\text{poly}\\log{n})$, and $(1+\\varepsilon)$-coreset for $k-$means and $k-$median.", "questions": "N/A.", "limitations": "", "rating": 6, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "The problem setting is very natural, for cases where distance computation might be hard or expensivem, performing comparisions using machine learning models might be efficient. The proofs are clear to the best of my knowledge. This work removes the requirement of distance oracle and provides coreset construction with only the oracle queries. The results obtained are near-optimal.", "weaknesses": "The experimental setting is very limited, with them being run on only one synthetic dataset. But the algorithmic contributions and results obtained are non-trivial and significant contribution so this is not really a major concern for me. Maybe a minor typo - probsort (in Lemma 2.1) requires noise parameter $\\leq 1/4$ but appendix A says $\\leq 1/2$.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "vvlNPRVju9", "reviewer": "Reviewer_y7gL", "summary": "The paper studied coreset algorithms with a noisy quadruplet distance oracle. Here, we are given $n$ data points in a metric space, and the distance metric $d$ is hidden from the algorithm. Instead, the algorithm could only make *comparison queries* in the form of ‘whether the distance $d(x,y)$ is smaller than the distance $d(u,v)$’. The oracle answers correctly with probability $1-p$ for some $p\\in(0,1/4)$, and the answer could be adversarial with probability $p$. The noise is persistent, meaning that if the oracle returns a wrong answer, we cannot query multiple times to get the correct answer. We want to understand what we can do for $k$-clustering with information from the noisy quadruplet oracle answers.\n\nThe motivation for this model is from a recent line of work using weak and strong oracle models, where the information obtained by the weak oracle is usually deemed as ‘cheap but inaccurate’ and the strong oracle simply returns the correct answer, but it is considered expensive to query. In many cases, the presence of a strong oracle is necessary, as shown by Galhotra, Raychaudhury, and Sintos [PODS’24], that we cannot hope to obtain $O(1)$-approximation for $k$-clustering with only the weak quadruplet oracle. \n\nThis paper, in contrast, shows that it is possible to construct *coresets* of size $k \\text{polylog}(n)$ using only the weak oracle. The catch here is that we might be able to output a subset of points that contains the information for $O(1)$-approximation $k$-clustering *without* knowing the actual clustering. On this front, the paper obtained an algorithm that achieves $O(1)$-approximation coreset of size $k \\text{polylog}(n)$ using only $nk \\text{polylog}(n)$ weak oracle queries. Furthermore, when the doubling dimension of the metric is bounded, the number of queries could be further decreased to $(n+k^2)\\text{polylog}(n)$.\n\n**Techniques.** The starting point of the techniques is quite simple: we know that if we sample $k \\text{polylog}(n)$ points in each iteration, filter out a tiny constant fraction of the vertex pairs with the longest distances, then the rest of the points would preserve the distances by an $O(1)$ factor. Therefore, if we simply want a coreset, we could just sample recursively and order the distances from the quadruplet oracle with some noisy sorting algorithm. The process terminates in $O(\\log{n})$ rounds, so we have coresets of size $k \\text{polylog}(n)$. However, if we want to generate a mapping between the points and their coreset points, then we will need to be more careful. In particular, the distances sorted by the noisy algorithm are not trustworthy, so the paper designed a more careful’’guard’’ set that basically serves as ‘distance witnesses’ to filter out points that are too close to the sampled points. For the rest of the points, since we could tolerate the radius of the kernel set distance, we could aggregate the information to compute an approximate neighbor for $v$ in the sampled set. This constitutes the main idea used in the paper.", "questions": "I have some slightly technical questions to help me understand the results better:\n- If we do not care about the mapping between points and the coreset, but we are still given the noisy oracle (as opposed to the perfect one), does it make the situation drastically easier? I believe it is the case since the dislocation error is at most $O(\\log{n})$, and the recursive process that eliminates O(1) fraction from the sampled sets is going to succeed with high probability. Is this correct, or did I miss anything?\n- For the points that do not get assigned to any sampled coreset point, e.g., the points in the kernel, do they simply survive for the next round of sampling? I guess this is the reason you want $|Kernel|<= V_i/\\text{polylog}(n)$, but I want to confirm.\n- Also, how large is the exponent on the logarithm terms? Do you have an upper bound?\n- Finally, line 264 says ‘For simplicity, we focus on the k-median objective (p = 1), but our approach extends naturally to $p>1$’ —-- I don’t really buy this. $k$-median costs have some nice linear properties that other clustering objectives might not have. Do you want to use generalized triangle inequality? You’ll lose a factor of $2^p$, though. Then, you’ll need to say that you assume $p=O(1)$.", "limitations": "", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "Overall, I like this paper. It follows the recent line of work for weak-strong oracle models. However, different from existing results that almost exclusively showed the necessity of the strong oracle, this paper is the first to show that we could do something without the strong oracle at all (as far as I know). I think this is a nice conceptual contribution. The paper is well-written, and although I did not get the time to check all the steps, the technical overview is easy to follow. Therefore, I would want to see the paper accepted into the conference.", "weaknesses": "I do not see any major weakness in the paper. One thing I want the author to emphasize is that one can know the coreset without knowing the clustering, since I was confused for a moment about whether there is a contradiction with GRS [PODS’24]. \n\nSome of the technical overview is a bit wordy and dense with math. I understand it’s a bit hard to present it in a cleaner manner. Maybe you can add some figures for the guard and kernel sets, plus the filtering process. I believe that’ll help readers understand.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "dQYrLx1wBl", "reviewer": "Reviewer_DLzD", "summary": "The paper studies metric k-clustering problems in the so-called Rank-model (R-model). In this model, we only have access to a noisy quadrupled oracle, i.e. an oracle that returns a correct answer to the question “is point A closer to B, or is C closer to D?” with probability phi. Since it it known that it is impossible to get any sublinear approximation for k-median and k-means problems in this setting, the paper presents algorithms that computes O(k polylog n) centers (and the corresponding mapping of the other points), whose corresponding k-clustering cost is a constant approximation of the optimal k-clustering cost, using only O(nk poly log n) oracle calls. \n\nThe paper further presents an improved algorithm with the same number of centers, but with a run-time of O((n+k^2)polylog n) for metrics whose doubling dimension is bounded. Then, an even better (1+epsilon) approximation algorithm is possible to obtain for k-median and k-means problems in these metrics. Finally, using these obtained centers from each of the above algorithms, one can also easily compute coresets for these clustering problems. \n\n** Technical Overview **\n\nThe generic algorithm follows a standard clustering approach by Mettu-Plaxton: we start by sampling a set S of O(k polylog n) points from the input set, and then order the remaining points by their distance to S. We then remove the closer half of these points, and recourse on the remaining ones. Of course, the biggest challenge is to find this ordering of the distances to S, since we don’t have an exact distance oracle. \n\nThe way to deal with this difficulty is to approximately sort the points in each step. Namely, if one uses a stronger notion of oracle, the so-called quadruplet oracle with adversarial noise, Raychaudhury (2025) showed that we can approximately sort these points by their distance from S. This oracle is similar to our weak oracle, but it returns the correct solution if the points are not too close, while it can return a false answer if the points are close. However, to be able to emulate this stronger oracle with our weaker quadruplet oracle, certain conditions must hold. Therefore, in all three algorithms, our goal is to find these conditions, and then exploit the above result. \n\nIn the general algorithm ALG-G, the algorithm first finds sets Kernel and Guard for each s in S. Guard points filter out the remaining input points that are too close to S, while Kernel points help us emulate the quadruplet oracle with adversarial noise. \n\nIn algorithm ALG-D we cannot afford to compute sets Kernel and Guard for each s in S. Instead, we first partition points in S into smaller parts, such that no two points in the same class are too close. With a slightly different filtering approach compared to ALG-G, we proceed in a similar manner to obtain the desired centers, now with respect to these parts. Finally, centers returned by ALG-D can be used to obtain clustering with better approximation by growing concentric balls around each of the centers, and exploiting the fact that the doubling dimension is bounded.", "questions": "What is the (intuitive) explanation why ALG-D fails in the general setting, i.e. where is the doubling dimension exploited?\n\n** Detailed technical comments **\n\nLine 24: from constant to epsilon -> to 1+epsilon?\nPage 3: definition of O(1)- and epsilon-coreset not consistent, the second condition missing in line 120?\nLemma 2.1: |E|=m missing\nBounds on phi not consistent, is phi < 1/4 or < 1/2?", "limitations": "", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "The paper is well-written and easy to follow.\nThe weak-oracle model is well motivated, and oracle-based modes in general have gained significant attention in the last few years.", "weaknesses": "While it is clear why ALG-DI required bounded doubling dimension, it is not entirely clear why ALG-D cannot be used in the general setting\nMinor technical comments (see Detailed technical overview)", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "cxjDN714em", "reviewer": "Reviewer_6phy", "summary": "This paper studies the metric k-clustering problem when only a weak comparison-based oracle (noisy oracle) is available. It introduces new representative centers construction method (with size $O(k poly\\log n)$) together with a mapping strategy. Using only quadruplet queries, this paper gives randomized algorithms that achieve: 1) in general metrics, an O(1)-Coreset+ (an extended notion of coreset with tighter guarantees) of size $O(kpoly\\log n)$ with $O(nk poly\\log  n)$ queries; 2) in bounded-doubling metrics, the same-size Coreset+ construction with $O((n+k^2) poly\\log n)$ queries; 3) for $k$-median/means objectives in doubling metrics, an $\\epsilon$-Coreset+ under the same query bound. The key techniques include probabilistic sorting under persistent noise with $O(logn)$ dislocation and an adversarial-oracle emulation using “kernel/guard” samples to produce 4-sorted orders and enable ANN selection. Overall, the framework shows how low-cost and noisy oracles can be integrated into scalable clustering algorithms designs.", "questions": "1. What are the tight query lower bounds for this problem under weak (noisy quadruplet) oracles? Whether the upper bounds provided in this paper can match these limits (up to logarithmic factors) for k-median/means, and if not, where is the gap?\n\n2. Since the paper focuses on general metrics, can the algorithms be further extended to low-dimensional Euclidean spaces—for example, achieving faster query complexities or stronger accuracy guarantees by leveraging geometric structure?", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "One of the paper’s key strengths is that it eliminates distance oracles entirely, which provides a clear breakthrough from RM-model work (e.g., Raychaudhury et al., 2025). This makes the proposed methods more practical in settings where exact pairwise distances are costly to compute, especially for high-dimensional or graph-based data settings. Building on the Coreset+ framework and using only quadruplet queries, the proposed method reduces computational complexities. It achieves query complexities of $O(nk poly\\log n)$ in general metrics and $O((n+k^2) poly\\log n)$ in doubling metrics, which are competitive with prior results while avoiding any distance computations.\n\nAdditionally, the algorithms are proved to remain within logarithmic factors of optimal bounds. Their techniques used, including probabilistic sorting and adversarial-oracle emulation, are new and interesting, which could have broader applications beyond clustering.", "weaknesses": "The weakness can be summarized as follows.\n\n1.Limited Experiments. While the authors present results on a synthetic 2D dataset, the empirical evaluation is limited to a single dataset with fixed parameters. There is no exploration of how the algorithm performs with varying parameters, dimensions, and noise levels. The paper would benefit from additional experiments with different datasets, noise rates, and metric spaces.\n\n2. Assumptions on noise. The paper assumes that noise across edge pairs is persistent and independent, which may not hold in practical settings. Some discussion of how to handle noise inconsistencies would improve the robustness of the proposed framework. \n\n3.Practical Efficiency: The constants involved in the query complexity could be high for large-scale datasets. More discussion on how to choose parameters (e.g., m_win, kernel sizes) for practical applications would strengthen the paper's relevance to practitioners.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "1sfzORnmbN", "reviewer": "Reviewer_yJGX", "summary": "The paper studies approximation algorithms for the $(k,p)$-clustering problem in the Rank-model (R-model), where instead of having direct access to pairwise distances, we have access to a (weak) oracle. This oracle takes two pairs of points, $(a,b)$ and $(c,d)$, as input and returns the pair that is closer. Furthermore, the oracle behaves probabilistically: it returns the correct answer with high probability (e.g., 99%) and is persistent. The task is to find a good solution to the $(k,p)$-clustering problem using as few oracle queries as possible.\n\nThe paper presents a bicriteria algorithm for the problem that opens $O(k (\\log n)^{O(1)})$ centers with an $O(1)$ approximation guarantee, using $O(nk (\\log n)^{O(1)})$ queries to the oracle in general metrics. Furthermore, the authors present improved results for metrics of bounded doubling dimension. To achieve their results, they design $O(1)$-“coresets” of size $O(k (\\log n)^{O(1)})$, also constructed with $O(nk (\\log n)^{O(1)})$ queries, which yields a bicriteria solution. The main technique appears to build on Har-Peled and Mazumdar (STOC ’04), which uses a recursive sampling subroutine to construct such coresets.", "questions": "1. This relates to Weakness #2. I am curious to understand how different the techniques are compared to existing work, particularly what new methods were required to adapt them to the R-model.\n2. It would be helpful to include a table summarizing the current state-of-the-art results for the problem (both in the R-model and RM-model) and to clearly highlight the contributions of this paper.\n3. On line 67: what is meant by “sublinear approximation”? Could you clarify this term?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. It is known that no constant-factor approximation is possible for $k$-median based solely on the R-model. In this context, the paper presents a promising approach that still achieves a constant-factor approximation, albeit by opening more than $k$ centers.\n\n2. Most of the results appear to extend to the adversarial oracle model, where the oracle is no longer probabilistic but adversarial, giving correct responses only when $d(a,b)$ and $d(c,d)$ are not very close to each other.\n\n3. The presentation is clear and well-organized, especially the technical section that highlights the main ideas of the algorithms.\n\n4. The experimental results are interesting and support the practical relevance of the proposed methods.", "weaknesses": "1. Although the paper achieves a constant-factor approximation using $O(k (\\log n)^{O(1)})$ centers, it is unclear whether the $\\log n$ term is necessary. Ideally, it would be preferable to obtain $O(k)$ centers, or alternatively, provide a lower bound showing that this is not possible.\n2. It is not clear how technically different their approach is compared to Har-Peled and Mazumdar, apart from the adaptation to the R-model.\n3. It is unfortunate that not a single proof appears in the main paper.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)