Pith. sign in

REVIEW 3 major objections 5 minor 1 cited by

Scalable k-Means Clustering for Large k via Seeded Approximate Nearest-Neighbor Search

T0 review · 3 major / 5 minor · reviewed 2026-08-08 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read SHEESH replaces Lloyd's exact reassignment with seeded approximate nearest-neighbor search, making million-center k-means on a single CPU practical for billion-point datasets.

desk verdict A genuinely new angle on large-k k-means assignment, with real engineering and a plausible CPU-vs-GPU story; the evidence is weaker than the prose, mostly because of time-limited curves and an internal contradiction about which variant wins. read the letter →

arxiv 2502.06163 v1 pith:EHXEOSDR submitted 2025-02-10 cs.LG cs.CGstat.ML

Jack Spalding-Jamieson , Eliot Wong Robson , Da Wei Zheng This is my paper · ORCID
classification cs.LGcs.CGstat.ML
keywords k-meansclusteringLloyd'salgorithmapproximatenearestneighborsearchseededsearch-graphlearning-augmentedalgorithmslarge-scaleHNSW
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This paper tackles k-means clustering when k is very large (up to a million centers) and the dataset is massive (up to a billion points), a regime where every Lloyd iteration costs $\Theta(|P| \cdot k)$ distance computations and known practical methods take at least $\Omega(k^2)$ overall. The authors argue that initialization is not the bottleneck in this regime; the assignment step is. They therefore recast the assignment step as a seeded approximate nearest-neighbor search (SANNS), in which each point's previous nearest centers serve as seed guesses, and they design a family of seeded search-graph methods to answer these queries. The resulting algorithm, SHEESH, is claimed to run on a single CPU and to outperform GPU implementations of Lloyd's algorithm in wall-clock time while reaching equal or better objective scores in every reported experiment, including a 12-hour run on SIFT1B with k=1,000,000.

What carries the argument

The load-bearing mechanism is the seeded search-graph: a sparse directed graph over the k centers (built on HNSW's hierarchical navigable small-world construction) in which beam search is initialized not from one arbitrary point but from a small set of seed centers, namely the point's top assignments from the previous Lloyd iteration. The seeds make the search a learning-augmented form of approximate nearest-neighbor search (SANNS): the method must work no matter the seed quality, but it speeds up when seeds are informative. Because centers move slowly after early iterations, the previous assignments are increasingly likely to remain near-optimal, so each reassignment costs only a short graph traversal instead of k distance computations; the grouped bulk ordering additionally reuses nearby results as extra seeds.

What would settle it

Run SHEESH and exact Lloyd from the same random initialization on a dataset with many close or overlapping centers (for example SIFT20M with k=100,000) for a fixed wall-clock budget, and compare the mean-squared-error objective; if exact or GPU Lloyd reaches a measurably lower objective in that budget, or if SHEESH's final objective exceeds exact Lloyd's after convergence, the central claim is falsified. The crucial control is identical random initialization and the same convergence criterion.

Watch

Extended reading notes

Core claim

The central discovery is that the exact nearest-center reassignment inside Lloyd's algorithm can be replaced by a seeded beam search over a graph built on the current centers, without sacrificing the quality of the final clustering. Previous-iteration assignments are kept as seeds (the paper stores the top 10 per point), so a query no longer compares against all k centers; it starts from likely centers and expands through the search graph. Three further heuristics make this practical: the search graph is rebuilt incrementally from the previous iteration's graph rather than from scratch, queries are processed in correlated groups sorted by a random 1-D projection so that results of one point seed the next, and beam search is forced to run a minimum number of iterations to avoid freezing into a premature local optimum. With these features, the paper reports that SHEESH achieved the best objective score in every experiment it ran, including k=100,000 on datasets with 5-20 million points and k=1,000,000 on SIFT1B, and that it improved on GPU Lloyd implementations in speed.

Load-bearing premise

The load-bearing assumption is that the seeded beam search over a graph of the current centers finds essentially the same best center as an exact scan, so that every Lloyd iteration makes the same progress it would with exact reassignment despite the approximation; the paper validates this only empirically, with no formal error bound for the full SHEESH heuristic.

Editorial extensions

If this is right

  • Large-k k-means can be run without GPU clusters: a single multi-threaded CPU can handle k near $10^6$ and n near $10^9$, with memory use scaling with k rather than requiring the whole dataset in RAM at once.
  • The runtime dependence on k in Lloyd's algorithm is no longer an inherent $\Theta(|P| \cdot k)$ barrier; assignment quality is maintained by seeding instead of by exact comparison with every center.
  • Out-of-core ANNS methods that rely on k-means for space partitioning can choose much larger k or avoid the $k^2 \approx |P|$ balancing tradeoff, because the clustering step itself is no longer quadratic in k.
  • Black-box ANNS alone was not sufficient; the decomposition into SANNS and bulk seeded search-graphs identifies seeding and batching of queries as the active ingredient that makes the speedup practical.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • Inference: if the search-graph framing is as general as the paper suggests, the same seeded-assignment idea could accelerate other centroid-based iterative algorithms, such as expectation-maximization for Gaussian mixtures, where previous responsibilities provide natural seeds.
  • Inference: recording the top 10 assignments probably helps not only because the previous best center is still near-optimal, but because the extra seeds give the beam search escape routes when a center moves; a direct ablation that varies the number of stored assignments would test this.
  • Inference: the paper's CPU results leave open whether hardware-accelerated graph search would preserve the speedup; if it does, the practical case for GPU k-means at very large k would weaken further.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

3 major / 5 minor

Summary. The paper proposes SHEESH, a modified Lloyd's algorithm for k-means clustering with very large k, which replaces the exact nearest-center assignment step with a seeded approximate nearest-neighbor search over a search graph built on the current centers. The authors introduce the Seeded Approximate Nearest-Neighbor Search (SANNS) and bulk variant (BSANNS) problems, argue that a naive black-box ANNS replacement is insufficient, and present a practical seeded search-graph algorithm with several heuristics (previous-assignment seeds, continuous graph rebuilds, minimum iteration counts, and grouping). Experiments on SIFT20M, Text2Image10M, and DPR5M with k from 10,000 to 100,000, plus a single 12-hour SIFT1B run with k=1,000,000, are used to claim that the CPU-only method achieves lower k-means objective values than GPU Lloyd baselines within a 500-second time limit. An appendix extends an existing theoretical search-graph analysis to SANNS, giving robustness and consistency guarantees for a Vamana-style graph.

Significance. If the empirical claims are correct, the paper addresses a genuine practical bottleneck: the O(|P|k) assignment cost of Lloyd's algorithm for large k. The problem formulation (SANNS/BSANNS) is a useful framing that may stimulate further work, and the authors ship code with reproduction instructions and document their experimental setup in detail. The Appendix D theoretical extension, while impractical for large k, is a legitimate and interesting observation. However, the central evidence is currently time-limited curves with no repeated runs, and one of the paper's own figures contradicts the stated 'best in every experiment' claim, so the significance is conditional on substantial empirical strengthening.

major comments (3)
  1. [Section 4.2 and Appendix C, Figure 8(d)] Section 4.2 states that 'our algorithm with all features enabled (sheesh [a]) achieved the best score in every single experiment we performed', and Appendix C repeats this claim. However, in Figure 8(d) (DPR5M, k=100,000), the legend is explicitly sorted by best score, and it lists sheesh [b] before sheesh [d], sheesh [c], and sheesh [a], indicating that sheesh [b] achieved a better score than sheesh [a] in that experiment. This is a direct internal contradiction. The authors should correct the claim, quantify the difference between sheesh [a] and sheesh [b] in this case, and discuss what it implies for the contribution of the continuous-rebuild feature.
  2. [Appendix C and Figures 4, 6, 7, 8] All headline comparisons are halted after 500 seconds, and at that cutoff the plotted objective curves are still decreasing. Consequently, a better score at 500 seconds conflates per-iteration speed with the quality of the local optimum that the algorithm will eventually reach. The central claim that SHEESH achieves 'comparable or better objective scores' than exact Lloyd requires evidence about solution quality at convergence, not just at a fixed time limit. Please provide at least one comparison on a tractable dataset where exact Lloyd and SHEESH are both run to convergence (or for a fixed number of iterations), and report the converged objective values.
  3. [Appendix B and Figures 4-8] The experiments report no repeated runs and no error bars. The initialization is uniformly random (Appendix B), and HNSW construction and seeded searches are randomized, so a single run per configuration could reflect a favorable draw. To support the main empirical claim that SHEESH beats GPU Lloyd, the paper should report multiple independent runs (e.g., 5-10 seeds) with mean/median and a measure of spread, or demonstrate determinism of the implementation.
minor comments (5)
  1. [Algorithm 1] The input line contains 'p* ∈ P' twice; the duplicate should be removed.
  2. [Appendix D, Theorem D.1] The theorem statement uses the malformed expression 'l logα 1+δ ϵ m'; it should be written as the ceiling of log base α of ((1+δ)/ε), and the surrounding proof should use this notation consistently.
  3. [Section 4.1] The claim that sorting by a random 1-dimensional projection has 'O(log n) distortion, as shown by Johnson & Lindenstrauss' is imprecise: the Johnson-Lindenstrauss lemma concerns embeddings into O(ε^{-2} log n) dimensions, and a one-dimensional projection does not in general provide that guarantee. Please clarify the intended statement or cite a more appropriate result.
  4. [Section 3.1] The note that 'there are some subtleties with some implementations of these methods (Grunau et al., 2023)' is too vague; please specify which implementations and which subtleties are relevant to the reported comparison.
  5. [Abstract and Section 1.1] The statement that 'all current practical methods for this problem have runtimes at least Ω(k^2)' should clarify whether it excludes the proposed method and any other search-graph-based approach, since the paper itself claims to mitigate this dependence; otherwise the sentence is ambiguous.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: SHEESH is evaluated against external baselines with untuned parameters, and the only theory result borrows an external theorem rather than a self-citation chain.

full rationale

The paper's central claim is empirical: SHEESH is compared against external implementations (scikit-learn, cuML, PyTorch GPU Lloyd, FAISS-based ANNS baselines) on public datasets, and the headline results are time-limited objective curves. The method's components are presented as heuristics, not as predictions derived from fitted parameters. The paper explicitly states that HNSW parameters and the top-10 seed count are not tuned per dataset ('There is almost certainly some improvement to be gained by better tuning these parameters to each dataset, but we have not done so'), which precludes the fitted-input-called-prediction pattern. The 'previous assignment as seed' idea is justified empirically via Table 1 and qualitative figures; it is a heuristic assumption, not a definitional equivalence. The theoretical result in Appendix D explicitly relies on an external theorem of Indyk & Xu (2023) and proves a conditional consistency bound, so it does not reduce to a self-citation or an imported uniqueness claim. No author self-citations are load-bearing. The only notable flaw is an internal inconsistency: the text claims 'our algorithm with all features enabled (sheesh [a]) achieved the best score in every single experiment', while Figure 8(d) legend is sorted by best score with sheesh [b] listed before sheesh [a]. This is a correctness/consistency concern about empirical reporting, not a circularity of the derivation. Overall, no step in the paper's claimed chain reduces by construction to its own inputs.

Assumptions & free parameters 6 free parameters · 5 assumptions · 0 invented entities

All heuristics rely on standard ANNS practice; parameters are hand-chosen defaults stated in Appendix C, not fit to the reported outcomes. The only external theory used is Indyk & Xu's VamanaSP analysis, which is cited and not self-authored. No new physical entities are introduced.

free parameters (6)
  • ef_build = 200
    HNSW build-time beam width, set to a 'sane default' (Appendix C), not tuned per dataset.
  • M = 60
    HNSW graph sparsity parameter, set by hand.
  • ef_search = 10 x num_prev_assignments
    Query-time beam width; scaled with the number of stored prior assignments.
  • min_iterations = 21 (2 x ef_search + 1)
    Minimum beam-search iterations at the lowest HNSW level to avoid premature termination.
  • num_prev_assignments = 10
    Number of previous best centers kept per point as seeds; authors say it has not been tuned.
  • prefetch_ahead = 4
    Number of vectors prefetched during beam search (Appendix E.1), chosen as a sane default.
assumptions (5)
  • domain assumption HNSW beam search (Algorithm 1) with these parameters yields accurate approximate nearest centers in practice for these datasets
    Relied on by the whole method; no guarantees are given for the heuristic SHEESH variant.
  • domain assumption Previous-assignment seed points are informative because centers move slowly between Lloyd iterations
    Supported only by Table 1 on SIFT1M k=5000, not proven for other datasets/k.
  • standard math Sorting randomly projected points in a group yields an ordering where consecutive points are likely to share a nearest center, so results can propagate as seeds
    Based on the Johnson-Lindenstrauss lemma (Section 4.1), but the heuristic step from distortion to cluster-correlated ordering is informal.
  • standard math Indyk & Xu (2023) VamanaSP guarantees apply with arbitrary start vertex
    Used in Appendix D to obtain robustness for free; cited rather than proven.
  • domain assumption Lloyd's algorithm fixed-point quality is preserved under approximate assignment
    The central empirical premise; the plots suggest it holds for tested cases, but there is no formal statement.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Scalable k-Means Clustering for Large k via Seeded Approximate Nearest-Neighbor Search." pith.science (2026). https://pith.science/paper/EHXEOSDR

@misc{pith2026250206163,
  author       = {Pith},
  title        = {Pith review of: Scalable k-Means Clustering for Large k via Seeded Approximate Nearest-Neighbor Search},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/EHXEOSDR}},
  note         = {Machine review of arXiv:2502.06163}
}
abstract

For very large values of $k$, we consider methods for fast $k$-means clustering of massive datasets with $10^7\sim10^9$ points in high-dimensions ($d\geq100$). All current practical methods for this problem have runtimes at least $\Omega(k^2)$. We find that initialization routines are not a bottleneck for this case. Instead, it is critical to improve the speed of Lloyd's local-search algorithm, particularly the step that reassigns points to their closest center. Attempting to improve this step naturally leads us to leverage approximate nearest-neighbor search methods, although this alone is not enough to be practical. Instead, we propose a family of problems we call "Seeded Approximate Nearest-Neighbor Search", for which we propose "Seeded Search-Graph" methods as a solution.

Figures

Figures reproduced from arXiv: 2502.06163 by the authors.

Figure 1
Figure 1. An illustration of the search path formed by Algo [PITH_FULL_IMAGE:figures/full_fig_p004_1.png] view at source ↗
Figure 2
Figure 2. Comparisons of different initialization methods for [PITH_FULL_IMAGE:figures/full_fig_p006_2.png] view at source ↗
Figure 3
Figure 3. Comparison of HNSW as a black-box method [PITH_FULL_IMAGE:figures/full_fig_p006_3.png] view at source ↗
Figures from the paper (5 more)
Figure 4
Figure 4. Figure 4: Comparison of our approach with GPU acceleration, as well as the black-box HNSW approach on the SIFT20M, [PITH_FULL_IMAGE:figures/full_fig_p008_4.png]
Figure 5
Figure 5. Figure 5: A plot of SHEESH running on SIFT1B with k = 1 000 000 for just over 12 hours. Initialization is uniformly random. We estimate SciKit-Learn would take roughly 9.5 days to run a single iteration in this case. a long time to compute a single iteration. Note also that the …
Figure 6
Figure 6. Figure 6: Comparisons of all methods on the Text2Image10M dataset, for all tested values of [PITH_FULL_IMAGE:figures/full_fig_p023_6.png]
Figure 7
Figure 7. Figure 7: Comparisons of all methods on the SIFT20M dataset, for all tested values of [PITH_FULL_IMAGE:figures/full_fig_p024_7.png]
Figure 8
Figure 8. Figure 8: Comparisons of all methods on the DPR5M dataset, for all tested values of [PITH_FULL_IMAGE:figures/full_fig_p025_8.png]

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

  1. PiPNN: Ultra-Scalable Graph-Based Nearest Neighbor Indexing

    cs.DB 2026-02 conditional novelty 6.0 of 10

    PiPNN builds high-quality approximate-nearest-neighbor search graphs up to 12.9x faster than HNSW and 11.6x faster than Vamana by replacing search-based construction with overlapping partitions, dense GEMM distance co...

Reference graph

Works this paper leans on

18 extracted references · 6 canonical work pages · cited by 1 Pith paper

  1. [1]

    (Optionally) use a sub-sampling technique to reduce the dataset size

    work page

  2. [2]

    Initialize the centroids

    work page

  3. [3]

    Use a local search technique to improve the solution

    work page

  4. [4]

    Each of these steps has a variety of avenues for improvement, see the survey by Ikotun et al

    Terminate after a pre-specified number of iterations or amount of time. Each of these steps has a variety of avenues for improvement, see the survey by Ikotun et al. (2023). For each, we will summarize only some of the most important methods potentially relevant to our case of large k. In particular, sub-sampling is quite limited for large k, since the nu...

    work page 2023

  5. [10]

    Simhadri, H

    URL https://proceedings.mlr.press/ v176/simhadri22a.html. Simhadri, H. V ., Aum ¨uller, M., Ingber, A., Douze, M., Williams, G., Manohar, M. D., Baranchuk, D., Liberty, E., Liu, F., Landrum, B., Karjikar, M., Dhulipala, L., Chen, M., Chen, Y ., Ma, R., Zhang, K., Cai, Y ., Shi, J., Chen, Y ., Zheng, W., Wan, Z., Yin, J., and Huang, B. Results of the big A...

    arXiv doi:10.48550/arxiv.2409.17424 2024

  6. [94]

    0000029664.99615.94

    URL https://doi.org/10.1023/B:VISI. 0000029664.99615.94. Ma, H. and Li, J. A true o(nlog n) algorithm for the all-k-nearest-neighbors problem. In Li, Y ., Cardei, M., and Huang, Y . (eds.),Combinatorial Optimization and Applications - 13th International Conference, COCOA 2019, Xiamen, China, December 13-15, 2019, Pro- ceedings, volume 11949 of Lecture Not...

    arXiv

  7. [139]

    Indyk, P

    URL https://www.sciencedirect.com/ science/article/pii/S0020025522014633. Indyk, P. and Xu, H. Worst-case performance of popular approximate nearest neighbor search implementations: Guarantees and limitations. Advances in Neural Informa- tion Processing Systems, 36:66239–66256, 2023. Jafari, O., Maurya, P., Nagarkar, P., Islam, K. M., and Cru- shev, C. A ...

    arXiv 2023

  8. [564]

    doi: 10.1109/ICDE53745.2022.00046

    IEEE, 2022. doi: 10.1109/ICDE53745.2022.00046. URL https://doi.org/10.1109/ICDE53745. 2022.00046. Zhao, W., Tan, S., and Li, P. SONG: approximate nearest neighbor search on GPU. In 36th IEEE International Conference on Data Engineering, ICDE 2020, Dallas, TX, USA, April 20-24, 2020, pp. 1033–1044. IEEE, 2020. doi: 10.1109/ICDE48307.2020.00094. URL https:/...

    arXiv 2022

Show all 18 references
  1. [1477]

    doi: 10.1109/ ICCV .2003.1238663

    IEEE Computer Society, 2003. doi: 10.1109/ ICCV .2003.1238663. URL https://doi.org/10. 1109/ICCV.2003.1238663. Sun, P., Simcha, D., Dopson, D., Guo, R., and Kumar, S. Soar: Improved indexing for approximate nearest neigh- bor search. Advances in Neural Information Processing S...

    2003 arXiv

  2. [2003]

    Friggstad, Z., Rezapour, M., and Salavatipour, M

    URL http://www.aaai.org/Library/ ICML/2003/icml03-022.php. Friggstad, Z., Rezapour, M., and Salavatipour, M. R. Local search yields a ptas for $k$-means in doubling metrics. SIAM Journal on Computing, 48(2):452–480, 2019. doi: 10.1137/17M1127181. URL https://doi.org/10. 1137/1...

    2003

  3. [2009]

    black-box

    for which Lloyd’s algorithm takes an exponential number of iterations to converge. Moreover, without a careful initialization, it may produce an arbitrarily bad clustering (Arthur & Vassilvitskii, 2006). Practical implementations often use a time limit or an iteration limit (s...

    2015

  4. [2010]

    URL https: //doi.org/10.1145/1772690.1772862

    doi: 10.1145/1772690.1772862. URL https: //doi.org/10.1145/1772690.1772862. Simhadri, H. V ., Williams, G., Aum¨uller, M., Douze, M., Babenko, A., Baranchuk, D., Chen, Q., Hosseini, L., Krishnaswamny, R., Srinivasa, G., Subramanya, S. J., and Wang, J. Results of the neurips’21...

  5. [2011]

    Approximation guarantees There has been prior work on providing approximation guarantees for the k-means problem using techniques related to local search

    implementation of k-means++, the reference implementation of k-means|| (Bahmani et al., 2012), and the cuML implementation of each (Raschka et al., 2020), all seem to be fairly slow on even moderately sized datasets. Approximation guarantees There has been prior work on provid...

    2002

  6. [2015]

    URL https: //doi.org/10.1109/CVPR.2015.7298596

    doi: 10.1109/CVPR.2015.7298596. URL https: //doi.org/10.1109/CVPR.2015.7298596. Gottlieb, L. and Krauthgamer, R. Proximity algorithms for nearly doubling spaces. SIAM J. Discret. Math., 27 (4):1759–1769, 2013. doi: 10.1137/120874242. URL https://doi.org/10.1137/120874242. Groh...

    2015

  7. [2017]

    URL https: //doi.org/10.1145/3132847.3133091

    doi: 10.1145/3132847.3133091. URL https: //doi.org/10.1145/3132847.3133091. Ikotun, A. M., Ezugwu, A. E., Abualigah, L., Abuhaija, B., and Heming, J. K-means clustering algo- rithms: A comprehensive review, variants analy- sis, and advances in the era of big data. In- formatio...

  8. [2020]

    Avrithis, Y ., Kalantidis, Y ., Anagnostopoulos, E., and Emiris, I

    URL https://github.com/erikbern/ ann-benchmarks/. Avrithis, Y ., Kalantidis, Y ., Anagnostopoulos, E., and Emiris, I. Z. Web-scale image clustering revisited. In 2015 IEEE International Conference on Computer Vi- sion, ICCV 2015, Santiago, Chile, December 7-13, 2015, pp. 1502–...

    2015

  9. [2022]

    URL https: //doi.org/10.1109/TPAMI.2021.3067706

    doi: 10.1109/TPAMI.2021.3067706. URL https: //doi.org/10.1109/TPAMI.2021.3067706. Gong, Y ., Pawlowski, M., Yang, F., Brandy, L., Bourdev, L. D., and Fergus, R. Web scale photo hash clustering on a single machine. In IEEE Conference on Computer Vision and Pattern Recognition, ...

    2021

  10. [9448]

    URL https: //doi.org/10.1109/TIT.1982.1056489

    doi: 10.1109/TIT.1982.1056489. URL https: //doi.org/10.1109/TIT.1982.1056489. Lowe, D. G. Distinctive image features from scale- invariant keypoints. Int. J. Comput. Vis. , 60(2):91– 110, 2004. doi: 10.1023/B:VISI.0000029664.99615

    1982

Pith tools

Reviewed August 8, 2026 · model on record in the stance chip above.