K-Means Clustering

K-means partitions a set of points into k clusters by alternating two steps: assign each point to its nearest centroid, then move each centroid to the mean of its assigned points. It minimizes within-cluster squared distance, and the centroid is exactly the mass-weighted mean of its members.

Streaming k-means

When points arrive one at a time and memory is fixed, the batch alternation is unavailable. The streaming variant keeps a bank of at most m centroids, each carrying a running sum and a scalar mass:

• Birth: while a slot is free, a new point becomes its own centroid.
• Merge: once full, a point folds into its Euclidean-nearest centroid, updating the sum and mass.
• Decay (optional): masses shrink over time, and a centroid dying below a floor frees its slot — the bank forgets.

The birth policy is the interesting design axis. Greedy fill (every point births while space remains) is simple and exact below capacity. DP-means-style policies instead birth only when a point is far from every centroid — spending capacity on novelty rather than arrival order — but are sensitive to how the distance threshold is normalized: anchor it on early garbage and nothing ever births.

Why it matters for attention

Softmax attention is kernel regression over keys: a query scores every stored key and mixes values by softmax weight. If keys cluster, attention over the clusters — mass-weighted centroids with a \log(\text{mass}) score correction — approximates attention over the tokens, exactly so when a cluster's members share a key. That observation is the basis of the K-Means Memory and Tiered Memory experiments, and of a family of published KV-cache compression schemes (Related Work).