You signed in with another tab or window. Reload to refresh your session.You signed out in another tab or window. Reload to refresh your session.You switched accounts on another tab or window. Reload to refresh your session.Dismiss alert
{{ message }}
Repository navigation
[Perf #478] KMeans Digits fit: eliminate 5.9x training deficit while preserving clustering equivalence #485
Canonical v2 Digits: Flow fit 351.94 ms vs sklearn 59.75 ms while Flow predict is faster (0.082 ms vs 0.132 ms). End-to-end is ~0.170x. Iris KMeans already wins ~6.7x, so the hole is scale-sensitive fit behavior.
Profile initialization, distance matrix/assignment, centroid accumulation, empty-cluster handling, convergence checks, restarts, allocation/copies and iteration count. Record distance evaluations and iterations so algorithmic work is separated from kernel throughput. Preserve the existing ARI/inertia semantic contract.
Acceptance: stage/iteration profile, operation counts, scaled samples/features/clusters/restarts, no regression in inertia/ARI parity, Digits fit >=0.95x first and >=1.05x target, current prediction win retained.
OpenProjects analysis found a concrete remaining initializer target in lib/scikit/cluster.flow: _kmeans_sk_pp_init samples all local-trial candidates for a center-selection step before scoring them, but then scores each candidate with its own scalar n × d_kmeans_sqdist pass. The same module already uses blas_matmat_nt for Lloyd assignment.
The greedy local trials can be scored in one batch without changing the random draw stream or exact real-arithmetic objective. Gather sampled candidate rows C, reuse one global xnorm[i] = ||x_i||^2 cache across all center selections and all n_init restarts, compute G = X C^T, then evaluate D_it = xnorm[i] + xnorm[c_t] - 2 G_it and P_t = sum_i min(closest[i], D_it).
For canonical Digits (n=1797, d=64, k=10, T=4, n_init=10), a simple feature-operation model drops from 124,208,640 scalar sub/mul/accumulate ops to 83,035,776 norm/dot ops, a structural reduction of 41,172,864 (~33.1%), before the throughput gain from moving the dominant work onto SGEMM.
Floating-point trajectory safety needs a guard: if approximate potential intervals satisfy P_hat[a]+E[a] < P_hat[b]-E[b] for every competitor, the winner is provably unchanged; otherwise fall back to the existing direct scorer for that selection step. This mirrors the guarded BLAS assignment strategy already in _kmeans_assign.
Full derivation + Flow executable: godofecht/OpenProjects/ml/batched-greedy-kmeans-plusplus.{md,flow}. The decisive profile is init sampling vs candidate scoring vs Lloyd, plus fallback rate and exact chosen-center sequence per restart.
Activity
godofecht commentedon Aug 24, 2026
OpenProjects analysis found a concrete remaining initializer target in
lib/scikit/cluster.flow:_kmeans_sk_pp_initsamples all local-trial candidates for a center-selection step before scoring them, but then scores each candidate with its own scalarn × d_kmeans_sqdistpass. The same module already usesblas_matmat_ntfor Lloyd assignment.The greedy local trials can be scored in one batch without changing the random draw stream or exact real-arithmetic objective. Gather sampled candidate rows
C, reuse one globalxnorm[i] = ||x_i||^2cache across all center selections and alln_initrestarts, computeG = X C^T, then evaluateD_it = xnorm[i] + xnorm[c_t] - 2 G_itandP_t = sum_i min(closest[i], D_it).For canonical Digits (
n=1797,d=64,k=10,T=4,n_init=10), a simple feature-operation model drops from 124,208,640 scalar sub/mul/accumulate ops to 83,035,776 norm/dot ops, a structural reduction of 41,172,864 (~33.1%), before the throughput gain from moving the dominant work onto SGEMM.Floating-point trajectory safety needs a guard: if approximate potential intervals satisfy
P_hat[a]+E[a] < P_hat[b]-E[b]for every competitor, the winner is provably unchanged; otherwise fall back to the existing direct scorer for that selection step. This mirrors the guarded BLAS assignment strategy already in_kmeans_assign.Full derivation + Flow executable:
godofecht/OpenProjects/ml/batched-greedy-kmeans-plusplus.{md,flow}. The decisive profile is init sampling vs candidate scoring vs Lloyd, plus fallback rate and exact chosen-center sequence per restart.