TL;DR
The recently proposed e-means algorithm aims to outperform standard k-means using mini-batch exponential averaging and cluster revival. However, this paper presents two 1D counterexamples showing that these very features can destroy globally optimal solutions and lead to an unbounded loss ratio compared to standard k-means, even when using k-means++ seeding.
What Problem Does This Paper Address?
Standard k-means (Lloyd’s algorithm) is the workhorse of clustering, but it’s computationally expensive on massive datasets because it requires multiple full passes over the data. To solve this, e-means (Bessa et al., 2026) introduced two main optimizations:
- Exponential Averaging: Updating cluster centers using mini-batches with a decay factor, allowing the algorithm to "learn" faster.
- Cluster Revival: If a cluster is "underutilized" (has too few points assigned to it), the algorithm "kills" it and restarts it near a more "active" cluster to avoid wasting resources on dead centers.
While e-means showed impressive results on high-dimensional embedding benchmarks, this paper asks a critical question: Are these heuristics robust? The author investigates whether the "published recipe" of e-means can fail in simple, low-dimensional settings where standard k-means succeeds.
Methods
The author uses a rigorous mathematical approach, constructing two specific 1D datasets designed to trigger the failure modes of e-means.
- Construction 1 (Revival Failure): A dataset with two dense clusters and one tiny, distant cluster. The author proves that e-means' mass-based revival rule will mistakenly identify the distant cluster as "dead" and reallocate its center, destroying the global optimum.
- Construction 2 (Forgetting Failure): A dataset where the order of mini-batches causes the decision boundary to "drift." Because exponential averaging gives less weight to older observations, the algorithm can "forget" a point it hasn't seen recently, allowing a boundary to cross over it and trapping the algorithm in a poor local minimum.
The paper also analyzes these failures under k-means++ seeding, a standard technique for finding good initial centers, to show that the problem lies in the algorithm's dynamics, not just bad luck at the start.
Datasets
The paper does not use standard large-scale benchmarks. Instead, it introduces two synthetic 1D benchmarks designed for explicit failure analysis:
- The Rare Cluster Family: Points placed at coordinates 1, 3, and a distant $D$. This is used to test the revival mechanism.
- The Eight-Point Example: A specific configuration of points at 0, 15, and 29 with varying multiplicities to test the "forgetting" effect of exponential averaging.
Key Insights and Ideas
- Mass is not Importance: The most striking insight is that "low usage" (few points) is a poor proxy for a "dead" cluster. In many real-world scenarios, a small, isolated cluster is exactly what you want to find. e-means' revival rule treats these as errors to be corrected.
- The Cost of Forgetting: Exponential moving averages introduce a "memory horizon." If a crucial data point isn't seen within a few batches, its influence on the cluster center vanishes. This can cause decision boundaries to move past points, leading to incorrect assignments that standard k-means would never make.
- Unbounded Failure: The author proves that the loss ratio (the error of e-means divided by the error of Lloyd's) can grow without bound as the dataset size increases.
Key Results
- Revival Destruction: In the first example, Lloyd's algorithm achieves a loss of 20, while e-means results in a loss of 110. As the number of points $m$ grows, the loss ratio becomes $\frac{m+1}{2}$.
- Expected Loss: Even with k-means++ seeding, the expected loss ratio remains unbounded ($> \frac{m+1}{6}$), as shown in the analysis of possible seed pairs.
- Boundary Drift: In the second example, the "forgetting" mechanism causes e-means to fail with a probability of 24/49 (~49%) on a simple 8-point dataset, resulting in an 8.89% higher loss than Lloyd's.
Limitations and Future Work
The author acknowledges that these are worst-case failures in one dimension. They do not claim that e-means fails frequently on the high-dimensional embedding benchmarks where it was originally validated. However, the results prove that the "published recipe" is not universally robust.
The paper notes that the community (specifically within the Faiss library) is already exploring more sophisticated revival policies, such as cost-based or separation-based revival, which might mitigate these issues. This work serves as a cautionary tale for designers of heuristic-heavy machine learning algorithms: simple usage metrics are often insufficient to justify drastic changes like removing a cluster center.
Summary updated