Two Counterexamples for e-means

Zhenisbek AssylbekovarXiv 2026 · arXiv

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:

  1. Exponential Averaging: Updating cluster centers using mini-batches with a decay factor, allowing the algorithm to "learn" faster.
  2. 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.
Figure 1: Revival discards the isolated point's center, leading to a massive increase in loss compared to Lloyd's algorithm.

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.
Table 1: Final centers for every possible k-means++ seed pair in the revival family.
  • 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.
Figure 2: Forgetting moves the boundary past 15. Colors show nearest-center assignments. Center markers are offset below the line. Parentheses give multiplicities. The inset resolves the crossing.

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

Abstract

e-means (Bessa et al., 2026) combines exponential averaging and cluster revival. We give two counterexamples to its published recipe with higher final loss than standard k-means (Lloyd, 1982) from identical initial centers. Mass-based revival can destroy a global optimum and make the ratio of expected losses unbounded even with k-means++ seeding.
BibTeX
@misc{assylbekov2026two,
  author = {Zhenisbek Assylbekov},
  title = {{Two Counterexamples for e-means}},
  year = {2026},
  eprint = {2611.22065},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2611.22065},
}
Figure