Computing k-means in mixed precision

Erin Carson; Xiaobo Liu; Xinye Chen

REVIEW 2 major objections 1 minor 1 cited by

Lloyd's k-means remains stable when distance computations drop to lower precision.

Reviewed by Pith at T0; open to challenge. T0 means a machine referee read the full paper against a public rubric. the ladder, T0–T4 →

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

T0 review · grok-4.3

2026-05-23 22:31 UTC pith:H5IJS6UU

load-bearing objection The paper shows through simulations that mixed-precision distances work in k-means for normalized data but need overflow care for unnormalized cases, without general bounds. the 2 major comments →

arxiv 2407.12208 v3 pith:H5IJS6UU submitted 2024-07-16 math.NA cs.NA

Computing k-means in mixed precision

Erin Carson , Xinye Chen , Xiaobo Liu This is my paper

classification math.NA cs.NA

keywords k-meansmixed precisionnumerical stabilityLloyd's algorithmdistance computationdata clusteringimage segmentation

verification ladder T0 review T1 audit T2 compute T3 formal T4 reserved

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper establishes that the standard distance formula used inside Lloyd's algorithm is numerically stable, then builds a mixed-precision framework that computes distances in reduced precision while keeping other steps in higher precision. Simulations on clustering tasks and image segmentation show that the approach produces results comparable to full precision, with normalized data tolerating the precision drop more readily than unnormalized data. A sympathetic reader would care because modern hardware offers fast low-precision units that could cut runtime and energy use for one of the most common clustering methods. The work therefore supplies concrete evidence that mixed-precision kernels can be swapped into k-means without immediate loss of correctness.

Core claim

We confirm the stability of the widely used distance computation formula. We propose a mixed-precision framework for k-means computation and investigate the effects of low-precision distance computation within the framework. Through extensive simulations on various data clustering and image segmentation tasks, we verify the applicability and robustness of the mixed precision k-means method. We find that, in k-means computation, normalized data is more tolerant to the reduction of precision in the distance computation, while for unnormalized data more care is needed in the use of reduced precision, mainly to avoid overflow.

What carries the argument

Mixed-precision framework that performs distance calculations in low precision inside Lloyd's iteration while retaining higher precision for other operations.

Load-bearing premise

The chosen simulation datasets and tasks represent the numerical behavior that will appear in other k-means workloads.

What would settle it

A dataset and cluster count where switching only the distance kernel to low precision produces measurably different final assignments or higher within-cluster sum of squares than the full-precision run.

Watch this falsifier — get emailed when new claim-graph text bears on it.

If this is right

Normalized input data tolerates lower precision in distance kernels with little change in clustering quality.
Unnormalized data requires safeguards against overflow when reduced precision is used for distances.
The mixed-precision distance kernel can be reused to accelerate other distance-based machine-learning routines.
Hardware support for low-precision arithmetic offers a practical route to faster k-means execution.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

If the stability holds beyond the tested cases, then k-means implementations on GPUs or AI accelerators could default to mixed-precision distances for an immediate performance gain.
The same distance-kernel substitution might be tested on streaming or online variants of k-means where data arrives continuously.
A natural next measurement is the exact speedup and energy saving on specific mixed-precision hardware when the framework is implemented in a production library.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit.

Desk Editor's Note

The paper shows through simulations that mixed-precision distances work in k-means for normalized data but need overflow care for unnormalized cases, without general bounds.

read the letter

The key point here is that the authors run simulations on clustering and image segmentation tasks and find that their mixed-precision framework for Lloyd's algorithm keeps results stable when data is normalized, while unnormalized data needs extra handling to avoid overflow in the distance formula. They confirm the standard ||x||² + ||y||² – 2 expression holds up numerically under reduced precision in their tests. That is the concrete new piece: the normalized-versus-unnormalized tolerance observation tied to a practical mixed-precision setup for this specific algorithm. The work applies known mixed-precision techniques to the k-means distance kernel and backs it with empirical runs on real tasks, which gives practitioners a usable data point on when lower precision is safe. The simulations appear to use standard datasets and report consistent behavior across the chosen examples. The main limitation is that the stability claim rests entirely on these task-specific runs. There are no analytic bounds on data norms, dimension, or cluster count that would tell you when the reduced-precision inner products stay faithful, and the paper itself flags overflow risk for unnormalized inputs without quantifying the safe regime. Because the verification stays within the tested distributions, it is possible that other workloads (high-norm data, very large k, or ill-conditioned cases) would show divergence not seen here. The methods details on exact formats and accumulation are summarized rather than fully expanded in the abstract, which leaves some uncertainty about reproducibility of the error behavior. This is the kind of paper that would interest people implementing clustering on mixed-precision hardware who want a quick empirical check rather than a full theory. A reader focused on numerical linear algebra or practical ML acceleration would get value from the normalized-data finding. It is solid enough on its own terms to deserve referee time, even if the central claim stays empirical. I would send it to peer review and ask for expanded methods, error-bar details, and perhaps a short discussion of when the approach is expected to break.

Referee Report

2 major / 1 minor

Summary. The paper claims that the widely used distance computation formula in Lloyd's k-means is numerically stable, proposes a mixed-precision framework for k-means, and verifies the applicability and robustness of low-precision distance computation within this framework via extensive simulations on data clustering and image segmentation tasks. It concludes that normalized data tolerates reduced precision better than unnormalized data, which requires care mainly to avoid overflow, and highlights potential for accelerating k-means with mixed-precision kernels.

Significance. If the empirical results hold, the work provides concrete evidence that mixed-precision distance kernels can be used to accelerate k-means while preserving stability on the tested workloads, offering practical insights for other distance-based ML algorithms. The explicit distinction between normalized and unnormalized data behaviors, together with the empirical validation against external datasets, strengthens the contribution in the context of emerging mixed-precision hardware.

major comments (2)

[Simulation and results sections] The central stability and robustness claims rest on the simulation results, yet the manuscript summarizes (rather than fully specifies) the exact precision formats, datasets, overflow handling, and error-bar analysis; this limits the ability to assess reproducibility and generality of the reported outcomes.
[Discussion and conclusions] No analytic bounds or conditions are derived on data norms relative to low-precision exponent ranges or on accumulation error in the ||x||² + ||y||² – 2<x,y> formula under varying k or dimension; while the paper is empirical, the absence of such guidance leaves open the possibility of divergence outside the tested regimes.

minor comments (1)

[Abstract and results] The abstract states that 'normalized data is more tolerant' but the corresponding quantitative comparison (e.g., failure rates or assignment differences) should be highlighted with a dedicated table or figure reference in the main text.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the positive assessment, the recommendation of minor revision, and the constructive comments on reproducibility and guidance. We address each major comment below.

read point-by-point responses

Referee: [Simulation and results sections] The central stability and robustness claims rest on the simulation results, yet the manuscript summarizes (rather than fully specifies) the exact precision formats, datasets, overflow handling, and error-bar analysis; this limits the ability to assess reproducibility and generality of the reported outcomes.

Authors: We agree that additional detail is required. In the revised manuscript we will add a new subsection that explicitly lists all precision formats employed (including FP32, FP16, and BF16), provides the full set of datasets with sources, dimensions, and preprocessing (normalization or lack thereof), describes the overflow-handling strategy (dynamic scaling when the exponent range is approached), and reports error bars obtained from multiple independent runs together with standard deviations. revision: yes
Referee: [Discussion and conclusions] No analytic bounds or conditions are derived on data norms relative to low-precision exponent ranges or on accumulation error in the ||x||² + ||y||² – 2<x,y> formula under varying k or dimension; while the paper is empirical, the absence of such guidance leaves open the possibility of divergence outside the tested regimes.

Authors: The work is deliberately empirical. We will expand the discussion section to supply practical, experiment-derived guidance on observed safe ranges of data norms relative to the tested exponent widths and to comment on accumulation behavior across the range of k and dimensions examined. We will also state explicitly that general analytic bounds are outside the paper’s scope and note the consequent limitation on extrapolation beyond the tested regimes. revision: partial

Circularity Check

0 steps flagged

No circularity: empirical validation against external datasets

full rationale

The paper's central claims rest on proposing a mixed-precision framework for Lloyd's k-means and confirming stability of the standard distance formula via direct numerical simulations on chosen clustering and segmentation datasets. No equations, fitted parameters, or predictions are defined in terms of the reported outcomes; the verification steps use external data and do not reduce to self-referential inputs or self-citation chains. The work is self-contained as empirical evidence without load-bearing derivations that collapse by construction.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The work rests on standard floating-point arithmetic properties and the assumption that the chosen simulation workloads exercise the relevant numerical regimes; no new entities or fitted parameters are introduced in the abstract.

axioms (2)

standard math Standard properties of floating-point arithmetic (IEEE 754 rounding, overflow behavior) govern the distance computations.
Invoked when discussing stability of the distance formula and overflow risk.
domain assumption The simulation data sets and tasks are representative of typical k-means workloads.
Required to extrapolate from the reported experiments to general applicability.

pith-pipeline@v0.9.0 · 5773 in / 1310 out tokens · 17720 ms · 2026-05-23T22:31:09.317633+00:00 · methodology

0 comments

read the original abstract

Motivated by the increasing availability of low- and mixed-precision arithmetic on modern hardware, we develop mixed-precision variants of Lloyd's algorithm for k-means clustering. The main ingredient is a family of mixed-precision kernels for Euclidean distance computation. 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 the accuracy and convergence behavior of higher-precision baselines. In particular, our CUDA implementations achieve orders-of-magnitude speedups over the CPU implementation in \texttt{scikit-learn} and up to $4\times$ faster than the IEEE double-precision \texttt{cdist} routine of \texttt{PyTorch} on NVIDIA A100 GPU, while providing improved numerical robustness in cancellation-prone regimes. The resulting mixed-precision k-means methods are effective for clustering and image segmentation, although the observed gains depend on the dataset, feature dimension, and number of clusters. These results demonstrate that mixed-precision distance kernels can offer a useful trade-off between performance and accuracy for k-means clustering and suggest that similar ideas may be beneficial for other distance-based machine learning methods.

Figures

Figures reproduced from arXiv: 2407.12208 by Erin Carson, Xiaobo Liu, Xinye Chen.

**Figure 5.1.** Figure 5.1: The difference measured as (5.6) of the two distance computing formulae (4.3) and (4.4) in double precision. and so the only worrying case implied from the bound is when (x − y) T (x − y) = x T x − 2x T y + y T y = d 2 r ≪ ∥y∥ 2 2 , ∥x∥2 ≈ ∥y∥2, which can happen only when the angle θ between x and y is close to 0 (the two vectors are aligned). However, we know from (5.4) that the forward error in computi… view at source ↗

**Figure 6.1.** Figure 6.1: The triggered rate η of low precision computations in terms of δ on synthetic Gaussian blobs data of different deviation σ, where 2,000 Gaussian data points with 10 clusters (blobs) are generated. 6.2. Simulations with various δ To gauge how many computations have been performed in a lower precision in computing the distance between a center and data points via Algorithm 6.2, we define and report when ne… view at source ↗

**Figure 6.2.** Figure 6.2: The performance in terms of ARI and AMI of Algorithm [PITH_FULL_IMAGE:figures/full_fig_p012_6_2.png] view at source ↗

**Figure 7.1.** Figure 7.1: Visualization of the S-sets (colors marked as ground truth clusters). [PITH_FULL_IMAGE:figures/full_fig_p014_7_1.png] view at source ↗

**Figure 7.2.** Figure 7.2: Tasks in images selected from ImageNet [PITH_FULL_IMAGE:figures/full_fig_p018_7_2.png] view at source ↗

**Figure 7.3.** Figure 7.3: Results of image segmentation for k-means++ in the working precision (fp64). phenomenon in the context of Euclidean distance computation is desired. Another future research direction could be providing stronger theoretical support for the use of mixed precision in distance computation and developing a more systematic approach of low precision switching mechanism. Acknowledgements The first and second aut… view at source ↗

**Figure 7.4.** Figure 7.4: Results of image segmentation I (fp16). [2] H. Jegou, M. Douze, C. Schmid, Product quantization for nearest neighbor search, IEEE Transactions on Pattern Analysis and Machine ´ Intelligence 33 (1) (2010) 117–128. doi:10.1109/TPAMI.2010.57. [3] M. Norouzi, D. J. Fleet, Cartesian K-means, in: 2013 IEEE Conference on Computer Vision and Pattern Recognition, IEEE, 2013, pp. 3017–3024. doi:10.1109/CVPR.2013.3… view at source ↗

**Figure 7.5.** Figure 7.5: Results of image segmentation I (q52). Proceedings of the 30th International Conference on Neural Information Processing Systems, Curran Associates Inc., New York, USA, 2016, pp. 1360–1368. doi:10.5555/3157096.3157248. [19] D. Sculley, Web-scale k-means clustering, in: WWW’10: Proceedings of the 19th international conference on World wide web, ACM Press, New York, USA, 2010, pp. 1177–1178. doi:10.1145/17… view at source ↗

**Figure 7.6.** Figure 7.6: Results of image segmentation II (fp16). [PITH_FULL_IMAGE:figures/full_fig_p021_7_6.png] view at source ↗

**Figure 7.7.** Figure 7.7: Results of image segmentation II (q52). URL https://dl.acm.org/doi/abs/10.5555/3524938.3525913 [48] J. Xu, X. Sun, Z. Zhang, G. Zhao, J. Lin, Understanding and improving layer normalization, in: H. M. Wallach, H. Larochelle, A. Beygelzimer, F. d’Alche-Buc, E. B. Fox (Eds.), NIPS’19: Proceedings of the 33rd International Conference on Neural Information Processing Systems, ´ Curran Associates Inc., 2019, … view at source ↗

discussion (0)

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score.

Automated Numerical Stability Analysis of Deep Learning Operators
math.NA 2026-07 conditional novelty 6.0

noisefloat integrates CESTAC stochastic validation into NumPy/PyTorch/JAX/TensorFlow and reports significant-digit losses per operator, detecting deliberately unstable operators in controlled image and text benchmarks.