KNN execution and validation

Development source change, October 30, 2026. No published runtime/editor version is implied.

Increment 1: serial kernel compatibility

One internal query engine serves predictions, probabilities and neighbor readouts. Existing fit/query signatures remain available and serial. The distance arithmetic retains ordered checked Float64 hypot accumulation. Selection retains nth_element and its distance/index total key. Uniform classification omits selected neighbor sorting because its integer counts are exact; neighbor inspection remains ordered. An independent full sort reference and the original preserved library establish compatibility.

Increment 2: bounded native executor integration

Explicit local CPU Float64 contexts reuse their native Executor. Lane identity owns preallocated scratch; each lane processes a balanced contiguous query interval and writes disjoint output rows. The configured pool keeps its CPU slot admission, including when fewer queries than workers are useful. No interpreter callback or new thread pool is used inside the KNN kernel. The default 64 MiB workspace admits output, vector capacities and bounded controls before dispatch; it is not an RSS limit. Context/observer variable payloads, existing executor internals, model/input data, Tensor leaf metadata, host caches, allocator overhead and OS stacks remain outside this scope. Cancellation joins before output publication. Logical query order determines numerical failure identity. Handle/options/context snapshots keep storage alive even if the native progress observer rebinds caller variables; mutating the underlying Tensor payload concurrently remains unsupported.

Increment 3: fitted inverse distance weights

fit_knn accepts an optional uniform/distance String and stores the policy immutably. Selected zero distance rows alone vote equally. For positive distances each class accumulates compensated sums relative to its nearest selected member. frexp/ldexp combine scales without overflowing reciprocals. Final probability normalization delays exponent scaling to preserve representable subnormal class probabilities. Accumulation and normalization orders do not depend on workers. Ties are equality of computed Float64 class scores, resolved by smallest class ID; exact real ordering below Float64 score resolution is not promised.

Complexity and boundaries

For N training rows, D features, Q queries, C classes, k neighbors and P active lanes, uniform expected work is O(QND + QN + Q(k+C)); weighted/ordered readouts add O(Qk log k). Selection has an average linear, not portable worst case linear, guarantee. Scratch is O(P(N+C)), plus output. No Q by N distance matrix is retained. Whole call QND and Tensor cell guards are unchanged. Existing calls do not automatically parallelize. GPU/cluster KNN, approximate/indexed search, public reusable neighbor results, model serialization and ahead of time Tensor/model lowering remain separate work.

Validation and measurement

Run the native and language KNN targets plus ML, tree, pipeline, parallel and conformance regressions. Native tests compare all readouts bitwise across worker counts and cover numerical extremes, workspace, cancellation, failure ordering and observer lifetime. Run ASan/UBSan separately. Editor signature/model documentation tests verify public argument labels and generated references.

Build the excluded from default aner_knn_benchmark target and run tools/knn_benchmark.py against it and a separately compiled pre change baseline using the same benchmark source with ANER_KNN_BASELINE defined. The driver retains binary/source hashes, raw samples, median/MAD, correctness checks and timing boundaries. Context reuse and cold context measurements are distinct. Fit and independent correctness checks are outside prediction timers. No speed threshold is a unit test assertion. An exploratory batch showed high process CPU cost from per candidate shared stop token copies; the final hot helpers borrow the callback owned token instead, preserving cancellation checks and numerical order. Before/after kernels and raw exploratory records are retained with the research validation artifacts. The recorded local evidence is linked from the KNN guide.

Reproduction helpers: native benchmark source and independent Decimal weighting oracle.

See the Machine learning module reference for the shared API.