For years, k-means clustering has been a one-off task. Engineers run it once to clean up data before training models, then discard it. That approach is dying in the age of modern AI. Researchers from UC Berkeley and UT Austin have released Flash-KMeans, an open-source library designed for a new reality: k-means is now embedded inside training and inference loops. When an algorithm runs thousands of times per second, the cost of a single call matters far more than the total number of floating-point operations.
Flash-KMeans is an IO-aware version of standard Lloyd’s k-means. It does not alter the underlying mathematics, nor does it use approximations. It simply restructures how data moves across a GPU. On an NVIDIA H200, the team reported an end-to-end speedup of up to 17.9× compared to the best existing baseline. Against NVIDIA cuML, the gain is 33×. Against FAISS, the library delivers over 200× faster performance.
What is Flash-KMeans
Flash-KMeans is a batched k-means library built using Triton GPU kernels. It is distributed under the Apache 2.0 license and installs via pip install flash-kmeans.
The output is mathematically identical to standard Lloyd’s k-means. The speedup stems from kernel-level dataflow, not from skipping calculations. This distinguishes it from algorithmic shortcuts like triangle-inequality pruning or coreset sampling.
A standard Lloyd iteration consists of two phases. The assignment phase calculates the distance from every point to every centroid, then selects the nearest one. The update phase averages the points within each cluster to generate new centroids. Both phases rely on simple arithmetic. On GPUs, both phases are throttled by memory bandwidth, not compute power.
The Two Bottlenecks It Attacks
The first bottleneck is the assignment phase. Conventional code constructs a full distance matrix D of shape N×K in High Bandwidth Memory (HBM). It writes the matrix, then reads it back to find the minimum value. For a dataset with N=65536 points, K=1024 clusters, and dimension d=128, the calculation itself takes 2.6ms. However, writing and consuming the matrix takes about 23ms. The memory traffic is the cost, not the math.
Flash-KMeans replaces this with FlashAssign. The design borrows concepts from FlashAttention. FlashAssign streams tiles of points and centroids from HBM into on-chip SRAM. It fuses distance calculation with an online minimum-finding operation. The full N×K matrix is never created. This reduces the dominant IO complexity from O(NK) to O(Nd + Kd). At the kernel level, FlashAssign achieves up to 21.2× speedup. In one test, it cut assignment time from 122.5ms to 5.8ms.
The second bottleneck is the centroid update phase. Standard code uses scatter-style atomic adds. Each thread adds its point into a shared sum buffer keyed by cluster id. Many threads frequently hit the same ‘hot’ cluster simultaneously. This causes atomic contention and hardware serialization. The research team measured only 50 GB/s effective bandwidth here on an H200.
Flash-KMeans replaces this with Sort-Inverse Update. It sorts the 1D assignment vector by cluster id using argsort. Identical cluster ids then form contiguous segments. Each thread block reduces a segment on-chip, then issues one atomic add per segment. The heavy point matrix is never physically permuted. Atomic operations drop from O((K + N/B)d). The kernel reaches up to 6.3× speedup.
Benchmark
The research team tested the software on an H200 with CUDA 12.8, FP16 data, and d=128. They swept N, K, and batch size B. They compared results against four optimized baselines: fast_pytorch_kmeans, fastkmeans, cuML, and FAISS.
| Comparison | Reported speedup | Workload context |
|---|---|---|
| End-to-end vs best baseline | up to 17.9× | N=8M, K=1024 (large N, small K) |
| vs NVIDIA cuML | 33× | industry library |
| vs FAISS | over 200× | industry library |
| FlashAssign kernel | up to 21.2× | N=1M, K=8192 (assignment) |
| Sort-Inverse Update kernel | up to 6.3× | N=33M, K=4096 (update) |
| Out-of-core, large scale | up to 10.5× | N=400M, K=16384 vs fastkmeans |
One failure mode is worth noting for context. Standard PyTorch implementations run out of memory in large-K regimes. They cannot materialize the N×K matrix. FAISS is the industry-standard library under many production vector-search systems.
The library also supports out-of-core processing. On one billion points (K=32768, d=128), it finishes an iteration in 41.4s, against 261.8s for the baseline. It uses chunked stream overlap to hide PCIe transfer behind compute. A cache-aware compile heuristic also cuts tuning overhead by up to 175×, staying within 0.3% of tuned speed.
Key takeaways
- Flash-KMeans achieves over 200× speedup against FAISS by restructuring GPU dataflow rather than altering the mathematical algorithm.
- The solution eliminates the need to materialise massive N×K distance matrices, reducing IO complexity from O(NK) to O(Nd + Kd).
- By sorting assignments before updating centroids, the library minimises atomic contention, boosting effective memory bandwidth from 50 GB/s to near-peak levels.
- The library handles out-of-core scenarios efficiently, processing one billion points in roughly two minutes on a single H200 GPU.
