{"id":"f29fe0bf-ae26-4f49-bdcd-3ce465de4b10","arxiv_id":"2607.08243","paper_version":1,"verdict":"CONDITIONAL","confidence":"HIGH","novelty_score":6.0,"correctness_risk":"low","formal_verification":"none","parameter_count":2,"one_line_summary":"GTRC stops k-means++ restarts once the min of a Good-Turing estimate, an unconditional 1/r bound, and a Clopper-Pearson confidence bound on improvement probability falls below ε/2.","lead":"GTRC decides when to stop restarting k-means++ by estimating the chance a new run would beat the best result so far, using Good-Turing plus two other bounds. It gives competitive clustering quality while adapting the restart count to each data set instead of using a fixed arbitrary number.","discovery_kind":"new_method","skeptic_critique":{"model":"grok-4.5","headline":"No significant objection identified beyond the paper's own caveat on the confidence bound.","rationale":"The paper's central claim is empirical and methodological rather than a claim of fully rigorous probabilistic control: GTRC produces competitive φ while letting restart count adapt to data difficulty via an interpretable signal. Theorems 1–2 and the unconditional bound 1/r are elementary and correctly derived; the Good-Turing term is used only as an upper bound on missing mass. The sole acknowledged gap is the selection bias in p★, which the reader already isolates. Because the min-of-three construction and the hard r_min=6 floor keep the procedure well-defined even when the confidence term is discarded, that gap does not undermine the reported competitiveness or the adaptive behaviour shown in Figures 1–3. The reader's CONDITIONAL verdict with high confidence is therefore already the right calibration; no further downgrade is warranted.","tokens_in":12182,"tokens_out":489,"duration_ms":5980,"concrete_test":"Re-run the full 36-dataset, 200-replicate protocol of Section 4 with the confidence term removed from U (i.e., U = min(φ₁/r, 1/r) only). If median objective gaps and Wilcoxon outcomes versus fixed-r baselines remain essentially unchanged, the approximation does not drive the headline claim.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The reader's weakest_assumption correctly flags the only material soft spot: the third (confidence) bound treats the currently best-observed partition as fixed when forming the Clopper-Pearson lower bound p_lo, even though that partition is selected from the same runs (Section 3.2 explicitly labels this \"an approximation rather than a rigorous guarantee\"). That bound is the one most often active at stopping (Figure 4: ~87%). However, the algorithm never relies on it alone; U is the minimum of three quantities, one of which (1/r) is unconditional and always valid by Theorem 1. Consequently the stopping decision remains sound even if the confidence term is optimistic, and the empirical claim (competitive quality with data-adaptive restart counts) is supported by the 36-dataset protocol. No deeper internal inconsistency or experimental confound appears load-bearing.","agreement_with_reader":"agree"},"referee_report":{"model":"grok-4.5","summary":"The paper proposes GTRC, a data-adaptive stopping rule for the number of k-means++ restarts. It upper-bounds the probability that a further independent run improves on the best objective seen so far by taking the minimum of three quantities: a Good–Turing missing-mass estimate, the unconditional bound 1/r from Theorem 1, and a Clopper–Pearson-based bound that treats the frequency of the current best partition as a binomial success probability. After a minimum of six restarts (motivated by Theorem 2), the algorithm stops once this minimum falls below ε/2. Across 36 UCI data sets (200 replicates each) the resulting objective values are competitive with fixed restart budgets of 10–100 while the realised restart counts vary substantially with data-set difficulty and track a lower confidence bound on the probability of the current best partition.","tokens_in":12415,"tokens_out":1097,"duration_ms":17026,"significance":"The work addresses a genuine and under-discussed methodological gap: the almost universal practice of fixing an arbitrary restart count and applying it uniformly across data sets of very different difficulty, which undermines both computational efficiency and the fairness of comparative baselines. The theoretical development (Lemmas 1–3, Theorems 1–2, Corollary 1) is elementary but correctly derived from i.i.d. runs and convexity, and the unconditional 1/r bound supplies a rigorous safety net. The criterion is interpretable (ε has a clear probabilistic reading), the software is released, and the experimental protocol (36 data sets, Wilcoxon tests on rounded objectives, reporting of which bound is active) is thorough. If the empirical claims hold under broader scrutiny, GTRC offers a reportable, principled alternative to fixed restart counts that clustering practitioners and benchmark authors can adopt immediately.","major_comments":[{"comment":"Section 3.2 explicitly labels the third (confidence) bound an “approximation rather than a rigorous guarantee” because the identity of the currently best partition is selected from the same sample used to form the Clopper–Pearson lower bound p_lo. Figure 4 shows this bound is the one most often active at stopping (~87 %). While the algorithm never relies on it alone—U is the minimum of three quantities, one of which (1/r) is unconditionally valid by Theorem 1—the paper should quantify, either analytically or by a controlled simulation, how often and by how much the approximation can be optimistic, and whether that optimism ever causes premature stopping relative to a pure 1/r rule on the same runs.","section":"Section 3.2 / Figure 4"},{"comment":"The unconditional bound 1/r implies a hard ceiling on the number of restarts once ε is fixed (r ≤ 2/ε). For ε = 0.05 this ceiling is 40; the text notes that half the data sets reach it. Consequently GTRC is fully adaptive only up to that ceiling. The manuscript should discuss more explicitly what a user should do when the algorithm hits the ceiling (e.g., whether to lower ε, accept the current solution, or switch to a different initialisation strategy), and whether the reported “competitive quality” on the hardest data sets is partly an artefact of this implicit fixed budget rather than of the adaptive signal alone.","section":"Section 5 / Figure 2"}],"minor_comments":[{"comment":"Title and first page: “fork-means++” is missing a space (“for k-means++”).","section":"Title"},{"comment":"Algorithm 1 line 13: the third term is written with p_lo, yet the surrounding prose sometimes uses p⋆; a single consistent symbol would improve readability.","section":"Algorithm 1"},{"comment":"Figure 1 caption and axis labels would benefit from an explicit statement that the “best observed objective” is the minimum over all methods and all 200 replicates for that data set, so that the reported gaps are relative to an empirical oracle rather than to a known global minimum.","section":"Figure 1"},{"comment":"The standardisation formula in Section 4 uses max − min in the denominator; a brief remark on how constant features (if any) are handled would avoid edge-case ambiguity.","section":"Section 4"},{"comment":"References [15] and [23] list access years 2026; if these are placeholders they should be updated to the actual retrieval dates before publication.","section":"References"}],"recommendation":"minor_revision","confidential_remarks":"The central technical contribution is modest but cleanly executed and immediately usable; the main risk is that the confidence-bound approximation, while mitigated, is the dominant stopping signal and is only lightly characterised. I do not see a load-bearing error that would justify rejection or major revision. Fit for a solid ML / data-mining journal is good; the paper is more “useful methodology” than “deep theory.”"},"author_rebuttal":null,"desk_editor":{"model":"grok-4.5","letter":"This is a clean engineering paper that solves a real annoyance: people still pick 10/20/50/100 restarts for k-means++ by habit and apply the same number to every data set. GTRC replaces that with a three-bound min (Good-Turing missing mass, unconditional 1/r from Theorem 1, and a Clopper-Pearson lower bound on the current best) that stops when the estimated improvement probability drops below ε/2, after a minimum of 6 runs justified by Theorem 2.\n\nWhat is new is the combination and the supporting lemmas, not the individual ingredients. Lemmas 1–3 and Theorems 1–2 are elementary (i.i.d. runs, Jensen, binomial ties) but correctly derived; the log growth of expected improvements is a useful observation. The experiments are transparent: 36 UCI sets, 200 replicates, Wilcoxon on rounded objectives, public code. Median quality matches well-chosen fixed counts while restart counts track p_lo almost perfectly (ρ ≈ −0.99) and range from 6 to the ε-implied ceiling. That is exactly the adaptivity claim the abstract makes.\n\nThe only material soft spot is the one the paper itself flags: the confidence bound treats the currently best partition as fixed when estimating p★, even though it is selected from the same runs. That bound is active ~87 % of the time. Because U is the min of three quantities and 1/r is always valid, the stopping decision remains sound even if the confidence term is optimistic. No deeper inconsistency or experimental confound appears load-bearing. ε and r_min are free parameters, but they are user tolerances, not fitted to the quality claim.\n\nThis is for anyone who runs or compares stochastic clustering and wants a reportable, data-dependent restart count instead of a magic number. It deserves a serious referee; I would cite it when I need a justified restart protocol. Send it out.","headline":"Solid, usable fix for arbitrary k-means++ restart counts; elementary theory, honest caveat on the dominant bound, experiments that actually show adaptivity.","tokens_in":12967,"tokens_out":511,"would_cite":true,"duration_ms":5103,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"grok-4.5","headline":"GTRC stops k-means++ restarts once the chance of a better result falls below a user tolerance, matching fixed-restart quality while letting the restart count adapt to each data set.","keywords":["k-means++","restart criterion","Good-Turing estimation","clustering","stopping rule","local optima","data-adaptive restarts"],"falsifier":"On data sets with known or tightly lower-bounded global optima, run GTRC at a stated ε many times: if it stops while still substantially above the optimum more often than ε allows, or if its final objectives are consistently worse than fixed-restart k-means++ that uses a comparable average number of restarts, the competitiveness claim fails.","tokens_in":13081,"feed_emoji":"🔁","tokens_out":959,"duration_ms":19419,"temperature":0.7,"pith_summary":"k-means++ is almost always restarted a fixed number of times chosen by habit and applied the same way to every data set. That wastes computation on easy data, can leave hard data under-served, and makes baselines sensitive to an arbitrary choice. This paper introduces GTRC, a stopping rule that estimates the probability another restart would beat the best partition found so far and halts when that probability drops below a user-specified tolerance ε. The estimate is the minimum of a Good–Turing missing-mass term, a proven unconditional bound of 1/r, and a confidence bound on the current best partition. On 36 data sets GTRC reached quality competitive with well-chosen fixed restart counts while using a restart count that varied with data-set difficulty. The result is a reportable, interpretable alternative to fixing the number of restarts in advance.","feed_headline":"Stop k-means++ restarts once they stop helping","feed_subtitle":"GTRC matches fixed-count quality on 36 data sets while using few restarts on easy data and more on hard data.","key_machinery":"GTRC: at each run r ≥ 6 it evaluates the minimum of the Good–Turing estimate φ₁/r, the unconditional bound 1/r from Theorem 1, and a Clopper–Pearson confidence bound that substitutes for the unknown probability of the current best partition; it stops when that minimum is ≤ ε/2.","core_discovery":"GTRC is a theoretically grounded, data-adaptive stopping criterion for k-means++ restarts. It combines three upper bounds on the probability that a further restart improves the best objective found so far, and stops once their minimum falls below ε/2 (after a minimum of six runs). Across 36 data sets it achieved clustering quality competitive with fixed restart counts of 10–100, while the number of restarts used varied appropriately with data-set difficulty under an interpretable, data-dependent signal rather than a fixed rule.","pith_inferences":["The same three-bound construction could be ported to other randomised clustering methods that produce i.i.d. objective values, not only k-means++.","Reporting ε and the final lower confidence bound p_lo alongside a clustering would let readers judge how confident a run was without re-running the algorithm.","If the Clopper–Pearson approximation is systematically biased on highly multimodal landscapes, a fully rigorous sequential test may be needed before libraries adopt GTRC as a default.","The logarithmic growth of expected improvements implies that very large fixed restart budgets are rarely justified once early improvements have already been observed."],"forward_implications":["Comparative studies can replace an arbitrary fixed restart count with a single interpretable tolerance ε, making baselines reportable and less sensitive to data-set difficulty.","Easy data sets automatically receive few restarts and hard ones more, cutting wasted computation while protecting quality.","Because the expected number of improving restarts grows only logarithmically, diminishing returns are theoretically expected and can be detected from the observed runs.","The unconditional 1/r bound alone guarantees eventual termination even when the Good–Turing and confidence bounds are not yet informative."],"fun_headline_variants":["GTRC halts k-means++ restarts once gains grow unlikely","Adaptive Good-Turing stop for k-means++ restart count","Restart k-means++ only while further gains stay likely","Data-dependent rule ends k-means++ restarts at right time","k-means++ restarts guided by odds of better optima"],"cache_read_input_tokens":128,"weakest_assumption_plain":"The confidence bound treats the currently best-observed partition as if its identity were fixed when estimating its probability from the same runs that selected it, which the paper itself calls an approximation rather than a rigorous guarantee.","fun_headline_variants_meta":{"raw":{"variants":["GTRC halts k-means++ restarts once gains grow unlikely","Adaptive Good-Turing stop for k-means++ restart count","Restart k-means++ only while further gains stay likely","Data-dependent rule ends k-means++ restarts at right time","k-means++ restarts guided by odds of better optima"]},"model":"grok-4.5","effort":"low","cost_usd":0.008008,"raw_usage":{"total_tokens":1920,"prompt_tokens":782,"num_sources_used":0,"completion_tokens":74,"cost_in_usd_ticks":80080000,"prompt_tokens_details":{"text_tokens":782,"audio_tokens":0,"image_tokens":0,"cached_tokens":256},"completion_tokens_details":{"audio_tokens":0,"reasoning_tokens":1064,"accepted_prediction_tokens":0,"rejected_prediction_tokens":0}},"tokens_in":782,"tokens_out":74,"duration_ms":9074,"temperature":1.0,"reasoning_tokens":1064,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-07-10T10:44:40.271666+00:00","model_set":{"reader":"grok-4.5"},"falsifier":"On data sets with known or tightly lower-bounded global optima, run GTRC at a stated ε many times: if it stops while still substantially above the optimum more often than ε allows, or if its final objectives are consistently worse than fixed-restart k-means++ that uses a comparable average number of restarts, the competitiveness claim fails.","supporting_citations":[],"review_version":1}