KMeans execution and validation

Development source implementation, October 30, 2026. The matching unreleased runtime/editor is required for the new arithmetic and optional local-execution/workspace overloads. Published Aner 0.0.5 keeps its earlier serial KMeans implementation. This source change does not publish packages, enable GPU/cluster KMeans or extend the bounded aner build Tensor/model subset.

Increment 1: corrected serial numerical kernel

The public model remains an immutable detached CPU Float64 snapshot containing centers, final fitting row labels, inertia, completed updates and convergence. Initialization still uses SplitMix64, signed seed UInt64 bit patterns and unbiased partial Fisher and Yates selection of distinct fitting row indices. Distinct indices may contain identical coordinates. Distance ties select the lowest center index; empty clusters retain their old centers. Absolute tolerance, the requested update cap and final reassignment against returned centers remain part of the contract.

An occupied centroid coordinate now accumulates the exact sum of its stored Float64 values, divides that integer representation by its member count and performs one nearest even rounding. ExactMean retains separate positive/negative 2176 bit magnitudes: 544 bytes in the current implementation. Its final division/rounding uses a 272 byte magnitude temporary. Cancellation among large signed terms therefore retains small representable residuals before division. This does not recover precision lost before values reached the model, including earlier Float32 rounding or preprocessing.

Final assignment still computes every checked distance in coordinate order with Float64 subtraction and hypot. ExactSquares accumulates the exact squares of those computed Float64 distances in a 4224 bit unsigned integer, using 528 bytes. Lane integer sums merge exactly; one final rounding produces inertia. Individual products do not first underflow or overflow. An unrepresentable final Float64 result fails. This is not an exact real coordinate difference sum of squares: the hypot results have already rounded.

Exact arithmetic changes the numerical baseline. Updated serial results can differ from the original scaled/compensated means and rounded product inertia, including convergence near a boundary. Tests compare updated serial with updated worker modes; they do not require the legacy algorithm's bits. The source keeps one seeded run, without K means++, restarts, a different metric, reduced precision or a global optimum guarantee.

Increment 2: bounded native prediction and execution infrastructure

Native KMeansOptions carries execution, max_workspace_bytes, a stop token and a progress observer. The language exposes execution and workspace controls on fit/predict; its five fitting parameters remain required. Shorter calls are serial and create no implicit context. An explicit local CPU Float64 context reuses its existing bounded executor. Incompatible GPU/cluster/precision contexts fail before worker dispatch.

One move only Executor::Session acquires exclusive context ownership and its full configured worker slot reservation for the entire fit, including coordinator work between phases. Other/nested submitters fail immediately rather than waiting or creating another pool. The configured workers are admitted concurrency, without core ownership or affinity guarantees. A phase can expose fewer useful lanes than the pool owns.

Prediction uses disjoint row ranges and detached output under these execution/workspace controls. Its configured pool can expose fewer useful lanes than it owns; one query supplies one row lane. The same session API supplies the operation lease needed by the later fitting increment. Updated serial and pool predictions retain coordinate ordered distance computation and lowest center index ties.

Increment 3: parallel fitting, stable CSR and memory control

The submitting thread sequences these stages:

1. Validate shape, parameters, full work bounds and workspace admission; retain input/options/context owners and select the original seeded initial rows.
2. Assign fitting rows in disjoint contiguous row ranges, reading immutable current centers.
3. Compare assignments, then build stable CSR cluster membership on the coordinator. The obsolete previous assignment buffer becomes the row ID membership buffer.
4. Assign independent (cluster,column) coordinates to lanes. Each lane reuses one exact mean accumulator over its cluster's members, writing only its next center coordinates.
5. Measure movement in the original checked coordinate order, swap old/next centers and assignment buffers, and apply convergence tests. Unchanged assignments can reuse their already exact centers while retaining the logical completed update count.
6. Release iteration capacities, allocate final labels, assign rows against final centers, accumulate exact squared computed distances per lane, and merge integers before publishing the completed model.

Each executor phase joins before the next starts. There is no worker barrier requiring every queued task to begin: cooperative cancellation can discard pending tasks safely. Prediction is one row parallel phase with disjoint detached output.

With W configured workers, row phases expose min(W,N) lanes, centroid phases min(W,kD), and prediction min(W,Q). Fit allocates enough lane storage for the maximum of its row/centroid counts. Integer accumulation and merge preserve centers, final labels, inertia, iteration/convergence metadata and predictions bitwise across updated serial and 1/2/4-worker execution in the same binary/floating-point environment. Platform math library differences remain outside that replay guarantee.

Capacity admission

The default positive max_workspace_bytes is 67,108,864 bytes (64 MiB). It is a cap, not a preallocated reservation. Preflight admits the whole call before dispatch and checks actual allocated capacities afterward. Insufficient budget fails without silently reducing worker concurrency. The requested maximum iteration count retains its full conservative work check even if convergence could occur earlier.

Fitting charges its new fitted centers/labels as output, iteration vectors, lane accumulators, bounded controls and explicit exact mean finalization temporaries. Prediction excludes its already fitted model while charging new output and lane controls. Numerical/index payload on a 64 bit index ABI has these phase shapes; actual sizeof, capacities and controls determine admission:

One variant per allocated fit lane contains either the 544 byte mean or 528 byte square accumulator, plus its discriminant/alignment and lane controls; the two accumulator payloads are not added together. Each simultaneously active mean lane additionally charges 272 bytes of finalization workspace. There is no N × k distance matrix or P × k × D accumulator storage. Fixed controls and exact temporary sizes are included in the capacity budget rather than described as unaccounted numerical scratch.

Input storage, Tensor host/readback caches, existing executor/session internals, observer/context payloads and strings, opaque shared ownership bookkeeping, allocator overhead, ordinary call stacks and OS thread stacks are outside charged workspace. The bounded mean temporary remains explicitly charged despite its local storage duration. The fitted model borrows pinned input values for the call and retains no full feature matrix copy. Charged bytes are not process RSS or a total heap peak.

Ownership, numerical environment and failure

Input/model handles, options and context configuration are copied before exposing native observers; the retained context keeps its executor alive. Rebinding caller handles/options from an observer is safe. Concurrent mutation of the underlying numerical Tensor payload remains unsupported. Each phase reports its own progress chunk counts on the submitting thread, without a promised whole fit percentage.

Coordinator, workers and observer boundaries establish/preserve the nearest even numerical environment, require gradual Float64 underflow and restore prior environments on return or failure. Progress callbacks cannot change later coordinator arithmetic by changing rounding mode. Stop requests are checked during distance, membership and centroid work and at phase/publication boundaries. Callback/task exceptions and cancellation join active chunks before staged buffers are destroyed. No successful partial model or prediction Tensor escapes.

Numerical failures are collected per lane rather than thrown immediately through the executor's cancellation path. Lower logical units continue; the lowest failing row or centroid coordinate unit is reported after joining. An external stop or observer exception can abort that operation separately. Busy contexts, nested work, invalid placement and capacity failures preserve the same joined ownership boundary.

Work bounds and scientific scope

For N fitting rows, D features, k clusters and I completed logical updates, exhaustive assignment plus final reassignment performs (I+1)NkD checked distance coordinate visits. Performed mean updates add O(N+k) CSR construction and O(ND) exact accumulation, while movement adds O(kD). Fixed width integer operations contribute bounded constant factors under the resource limits. Overall work remains O((I+1)NkD); concurrency does not reduce its asymptotic work or guarantee acceleration. A tiny fit, one center/coordinate, skewed memberships and pool startup can limit useful parallelism.

Tensor shapes retain the 1,000,000 element limit. Fitting retains (max_iterations+1)NkD ≤ 50,000,000; prediction retains QkD ≤ 50,000,000. The fitting guard counts assignment distance coordinates including finalization, not centroid, movement or integer operations. It is neither a FLOP count nor a wall clock guarantee.

Fit workspace is O(N+kD+k+PB), where P is allocated lanes and B is bounded exact-accumulator/control storage, with active mean temporaries also charged. Retained state is O(N+kD). Prediction uses O(QkD) work and O(Q+min(W,Q)) output/control storage. The getters copy center/label values. Feature preparation, explicit scaling and held out experimental design remain the caller's responsibility; cluster IDs are arbitrary indices rather than class predictions.

Validation and measurement reproduction

The complete native execution example compares all fitted properties and predictions with the updated serial algorithm. The KMeans guide gives every argument, interpretation and availability boundary.

Meaningful checks include exact rounding/cancellation and subnormal aggregates; repeated seed/row order; distance ties and empty clusters; final readouts at iteration/tolerance stopping; all returned bits and metadata across workers; byte budget admission boundaries; deterministic error identity; in flight cancellation; observer exceptions/handle rebinding/rounding changes; and whole session CPU/exclusivity preservation. Run the native KMeans, language, exact arithmetic, executor session, existing ML/KNN/tree and broader parallel regressions, with sanitizer runs kept separate from timing.

The Fraction arithmetic oracle and integration oracle independently inspect the exact arithmetic and whole model fixtures. Their scope includes stored binary64 inputs and squared computed distances; passing fixtures do not establish global clustering quality or platform independent math library bits.

Build the excluded from default aner_kmeans_benchmark target. The sequential driver compares it with a separately built preserved legacy kernel using the same native harness, with ANER_KMEANS_BASELINE defined only for the old kernel. Retain source/binary/compiler identities, raw samples, completed iterations, convergence, correctness checks and timing boundaries. Original serial, updated serial, reused one/two/four-worker pools and cold pools are distinct modes. Fit timing includes initialization, updates, final labels/inertia and workspace allocation; prediction timing excludes fitting. Pool setup modes need their own measurements.

Report median and median absolute deviation separately from correctness. Compare parallel scaling against the updated serial algorithm as well as the original kernel, since improved arithmetic can change both per update cost and iteration count. A fixed one update case helps separate those effects. Exact budget workspace probes, allocator accounting and fresh process peak RSS answer different questions and require separate labels. No speed threshold is a unit test assertion, and no timing or memory measurement is supplied by this design note.

The recorded local study retains legacy/updated serial and reused/cold worker observations for all nine workloads, separate workspace/RSS evidence, the standalone figure, and raw JSON.

See the Machine learning module reference for the shared API.