Paperlane

no. 16 · Tuesday 17 November 2026

Mixed-Precision Lloyd's Algorithm for k-means Clustering

Erin Carson, Xinye Chen and Xiaobo Liu

math.NA · v4

Abstract

As low-precision arithmetic becomes more widely available on modern hardware, we develop mixed-precision variants of Lloyd's algorithm for k-means clustering, with a family of mixed-precision kernels for Euclidean distance computation as the main ingredient. These kernels are guided by rounding-error analysis and use a simple reliability test to decide whether the expanded distance formula can be evaluated safely with low precision or a higher-precision correction by the direct distance formula is required. Thus, most distance computations can be carried out with low precision, while high-precision arithmetic is used selectively when cancellation may lead to a loss of accuracy. We evaluate the proposed methods on large-scale distance-computation benchmarks, synthetic clustering problems, and image-segmentation tasks. The experiments verify that the mixed-precision kernels on GPUs can substantially improve performance while retaining accuracy and convergence behavior of higher-precision baselines. In particular, our implemented distance computation in CUDA achieves speedups of up to $4\times$ over the \texttt{PyTorch} baseline that evaluates the expanded formula in FP64 on an NVIDIA A100 GPU, with overall maximum relative errors of order $10^{-3}$, while providing increased numerical robustness in cancellation-prone calculations. The resulting mixed-precision kernels show efficiency for clustering and image segmentation, although the observed gains depend on factors such as feature dimension, and number of clusters. The mixed-precision kernels offer a favorable trade-off between performance and accuracy for clustering, and suggest that similar ideas may be beneficial for other distance-based machine learning methods.

fields
Numerical Analysis
pdf ↗ page arXiv:2407.12208 ↗