Skip to content

[Perf #478] KMeans Digits fit: eliminate 5.9x training deficit while preserving clustering equivalence #485

Open

Description

@godofecht

Parent: #478

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.

Activity

  1. godofecht commented on Aug 24, 2026

    @godofecht
    OwnerAuthor

    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.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Metadata

Metadata

Assignees

No one assigned

    Labels

    No labels
    No labels

    Projects

    No projects

      Milestone

      No milestone

      Relationships

      None yet

      Development

      No branches or pull requests

      Issue actions