betaFeedback

WorksComputer Science

Two Counterexamples for e-means

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.

Introduction

Standard k-means alternates between assigning the full dataset to its nearest centers and recomputing exact cluster means ([4]). These repeated passes make clustering large collections of embeddings costly. Bessa et al. [2] propose e-means, which updates centers by mini-batch exponential averaging and revives centers with low estimated usage. On a wide array of embedding benchmarks, they report losses below those of 25-epoch Lloyd after 1.4–2.6 epochs.

Both modifications change which observations determine the centers. An observation absent from a batch can affect the optimal partition, while a small, distant cluster can be costly to merge.

Our main construction shows that mass-based revival can destroy a globally optimal solution. For the published parameter laws, e-means’ loss ratio to Lloyd grows without bound, including the ratio of expected losses under shared k-means++ seeding (Corollary 1). An eight-point example then illustrates how forgetting changes a previously observed point’s assignment and leads to a worse Lloyd fixed point. Its exact conditional failure probability is certified in Appendix § 5.

Our contribution is an explicit failure analysis of the published e-means rule: the revival family extends the rare-cluster failure reported by Sahai [5] with an unbounded loss separation. Related Faiss proposals introduce separation-based and cost-based revival ([6, 3]); our results concern the original mass-based rule.

Bessa et al. [2] already acknowledge limitations of their scaling laws on tiny datasets and data of low intrinsic dimension. Our constructions have intrinsic dimension one. They identify worst-case failure mechanisms within that regime; they make no claim about failure frequencies on embedding benchmarks.

Let X=(x1,…,xn)X = (x_1, \ldots, x_n) be a dataset of nn observations in Rd\mathbb{R}^d, allowing repeated values. Let C=(c1,…,ck)C = (c_1, \ldots, c_k) denote kk cluster centers in the same space. We measure the training sum of squared distances to the nearest center,

Φ(C)=∑i=1nmin⁡1≤j≤k∥xi−cj∥2.\Phi(C) = \sum_{i=1}^{n} \min_{1 \le j \le k} \lVert x_i - c_j \rVert^2.

Write Φ⋆=min⁡CΦ(C)\Phi_\star= \min_C \Phi(C) for the global optimum. Throughout, we analyze the printed recipe of Bessa et al. [2]: exact nearest-center assignments, the knee at 0.2%0.2\% batch law, initial counts Nj=10−10N_j = 10^{-10} and sums Sj=NjcjS_j = N_j c_j, revival every five batches at threshold 0.1/k0.1/k of total count, and last-epoch mean finalization. We specify initial centers below; Corollary 1 replaces random-row initialization with shared k-means++ seeding. Section 2 distinguishes the printed settings from the pinned library defaults used for validation.

Revival removes the center of a rare cluster

For e-means, let njn_j and sjs_j be the count and coordinate sum assigned to cluster jj in a batch. Its stored count NjN_j and sum SjS_j are updated as

Nj←(1−αt)Nj+αtnj,Sj←(1−αt)Sj+αtsj,cj=Sj/Nj.N_j \leftarrow(1-\alpha_t)N_j+\alpha_t n_j,\qquad S_j \leftarrow(1-\alpha_t)S_j+\alpha_t s_j,\qquad c_j=S_j/N_j.

Old assignments lose weight at each update.

Put ten observations at 1, ten at 3, and one at 14. Start both algorithms at (1,14)(1,14). Lloyd reaches the optimal centers (2,14)(2,14) in one full pass and stays there. Its squared error is 10(1−2)2+10(3−2)2=2010(1-2)^2+10(3-2)^2=20, and the point at 14 has zero error.

We set T=210T=210 epochs so that the printed parameter laws select full batches and a first step of size one, as verified below. e-means initially reaches the same optimal centers. Yet at batch 5 it declares the center at 14 dead. Its share Nj/∑ℓNℓ=1/21N_j/\sum_\ell N_\ell=1/21 is only 4.76%, below the revival threshold 0.1/k=5%0.1/k=5\% for k=2k=2 [2 Appendix H]. The rule therefore destroys a globally optimal solution.

Faiss splits a live donor to replace the center at 14. Its only donor is the center at 2. The two new centers lie just to either side of 2, so the ones go left and the threes and 14 go right. Their final means are (1, 4), giving squared error 110 (Figure 1). Disabling revival retains Lloyd’s loss 20.

Figure 1. Revival discards the isolated point’s center. The final centers are (1, 4), and the point at 14 contributes 100 of the total loss 110. Lloyd keeps its own center at 14 and has loss 20.

How large can the loss be? Replace ten by an integer m≥10m \ge10 and 14 by D=m+4D=m+4.

Proposition 1. Put mm observations at each of 1 and 3, and one at D=m+4D=m+4. Let n=2m+1n=2m+1, k=2k=2, and T=10nT=10n. From the shared initial centers (1,D)(1,D), the printed recipe returns (1,4)(1,4), while Lloyd reaches the global optimum (2,D)(2,D) in one pass. The loss ratio is (m+1)/2(m+1)/2, for any donor-split perturbation 0<δ<1/20<\delta<1/2.

Proof. We choose T=10nT=10n to make the printed laws select full batches and a unit first step. Specifically, the unrounded batch law and the unclipped peak-step law at B=nB=n satisfy

Brawn=0.035⋅20.13⋅100.81n0.69>2,\frac{B_{\mathrm{raw}}}{n}=0.035\cdot2^{0.13}\cdot10^{0.81}n^{0.69}>2,
α~0=0.824⋅2−0.46⋅10−0.11n0.34>1.\widetilde{\alpha}_0=0.824\cdot2^{-0.46}\cdot10^{-0.11}n^{0.34}>1.

At n=21n=21, the values exceed 2.0208 and 1.3092, respectively, and both increase with nn. Rounding BrawB_{\mathrm{raw}} to the nearest power of two and capping at nn therefore gives B=nB=n; clipping the peak gives α0=1\alpha_0=1. All later cosine-scheduled steps lie in (0,1)(0,1). The first update reaches (2,D)(2,D), with counts (2m,1)(2m,1). This state persists until the first revival check, which removes the singleton’s center because 1/(2m+1)<0.051/(2m+1)<0.05. The donor splits into 2(1−δ)2(1-\delta) and 2(1+δ)2(1+\delta), following Bessa et al. [2]. The ones go left, and the threes and DD go right. The left center then remains in [1,2)[1,2), and the right in (2,4](2,4], moving toward (3m+D)/(m+1)=4(3m+D)/(m+1)=4. Their midpoint stays strictly between 11 and 33, so these assignments persist.

Both children receive half the donor’s count, hence start at mm. Subsequent counts remain in [m,m+1][m,m+1], so each share is at least m/(2m+1)>0.05m/(2m+1)>0.05. Revival never triggers again. Final-epoch averaging therefore returns (1,4)(1,4).

The two cuts between distinct data values have costs

ΦLloyd=Φ⋆=2m,\Phi_{\mathrm{Lloyd}}=\Phi_\star=2m,
Φe-means=m(3−4)2+(D−4)2=m(m+1),\Phi_{\mathrm{e\text{-}means}}=m(3-4)^2+(D-4)^2=m(m+1),
Φe-meansΦLloyd=m+12.\frac{\Phi_{\mathrm{e\text{-}means}}}{\Phi_{\mathrm{Lloyd}}}=\frac{m+1}{2}.

These costs establish global optimality of (2,D)(2,D) and the claimed ratio. The returned centers (1,4)(1,4) have midpoint 5/25/2, making them a Lloyd fixed point as well. Thus the ratio grows without bound even though every batch contains the rare point.

Shared k-means++ seeding. The separation also holds in expectation over a standard randomized initialization.

Corollary 1. For the family and settings of Proposition 1, give both algorithms the same initial centers drawn by standard k-means++ seeding. Then

E[Φe-means]=m(m+1),E[ΦLloyd]<6m,E[Φe-means]E[ΦLloyd]>m+16.\mathbb{E}[\Phi_{\mathrm{e\text{-}means}}]=m(m+1),\qquad\mathbb{E}[\Phi_{\mathrm{Lloyd}}]<6m,\qquad\frac{\mathbb{E}[\Phi_{\mathrm{e\text{-}means}}]}{\mathbb{E}[\Phi_{\mathrm{Lloyd}}]}>\frac{m+1}{6}.

The expectations are over seeding, and the ratio is unbounded already for k=2k=2.

Proof. k-means++ selects its first center uniformly at random from the observations and the second in proportion to squared distance from it ([1]). Repeated values have zero distance to an existing center, so the possible seed pairs, up to ordering, are exactly those in Table 1.

Initial centerse-meansLloyd
(1,3)(1,3)(1,4)(1,4)(1,4)(1,4)
(1,D)(1,D)(1,4)(1,4)(2,D)(2,D)
(3,D)(3,D)(1,4)(1,4)(2,D)(2,D)

Table 1. Final centers for every possible k-means++ seed pair in the revival family.

For (1,3)(1,3), the first full-batch update reaches (1,4)(1,4), with counts (m,m+1)(m,m+1); the assignments persist and revival never triggers. For either pair containing DD, the first update reaches (2,D)(2,D), followed by the revival failure proved above. Thus e-means always returns (1,4)(1,4). With revival disabled, full-batch e-means agrees with Lloyd for every seed pair in Table 1. Thus revival causes the expected-loss separation.

Lloyd returns the worse solution only when the seed pair is (1,3)(1,3). This event has probability

qm=4m22m+1[1(m+3)2+4m+1(m+1)2+4m]<4m.q_m=\frac{4m^2}{2m+1}\left[\frac{1}{(m+3)^2+4m}+\frac{1}{(m+1)^2+4m}\right]<\frac{4}{m}.

The two terms correspond to the first seed being 11 and 33. Each denominator exceeds m2m^2, giving the bound. Consequently,

E[ΦLloyd]=(1−qm)2m+qmm(m+1)=2m+qmm(m−1)<6m.\mathbb{E}[\Phi_{\mathrm{Lloyd}}]=(1-q_m)2m+q_m m(m+1)=2m+q_m m(m-1)<6m.

Since Φ⋆=2m\Phi_\star=2m, Lloyd’s expected approximation ratio is below 33, while e-means’ ratio is (m+1)/2(m+1)/2. The mass-based revival rule can therefore forfeit the expected approximation guarantee supplied by k-means++ seeding.

Implementation. We validated all three seed pairs for m=10,20,50m = 10, 20, 50 using NumpyEmeans at Faiss revision 2b648f0, with explicit T=10nT = 10n, B=nB = n, α0=1\alpha_0 = 1, and enumerated seeding probabilities exactly. Its automatic recipe gives B=4B = 4, α0≈0.3013\alpha_0 \approx0.3013 at n=21n = 21, T=210T = 210, d=3d = 3. Its initial count 2−162^{-16} is erased by the unit first step. Because revival is disabled by default for d≤2d \le2, the checks use x↦(x,0,0)x \mapsto(x, 0, 0), preserving distances, donor splits, and intrinsic dimension one.

Code availability. Standalone code reproducing both counterexamples, the exact k-means++ expectations, and the interval certificate is available at https://github.com/zh3nis/e-means-counterexamples/.

Forgetting moves a boundary past an absent point

Use two clusters and start both algorithms at

X=(0,0,15,29,29,29,29,29),(cL,cR)=(15,29).X = (0,0,15,29,29,29,29,29), \qquad(c_L,c_R) = (15,29).

The initial midpoint is 22, so 15 joins the two zeros. Lloyd reaches (5,29)(5,29) in one pass and stays there, with boundary 17 and squared error 2(0−5)2+(15−5)2=1502(0-5)^2 + (15-5)^2 = 150. This is the optimum. The other cut puts 15 with the five copies of 29, at a cost of 56(29−15)2=490/3\frac{5}{6}(29-15)^2 = 490/3.

We use 25 epochs, each a full pass through the data. The batch law gives two batches of four per epoch, hence 50 updates. The published peak-step law and cosine schedule give

α0=0.824⋅2−0.46⋅40.90⋅8−0.45⋅25−0.11=0.574306…,\alpha_0 = 0.824 \cdot2^{-0.46} \cdot4^{0.90} \cdot8^{-0.45} \cdot25^{-0.11} = 0.574306\ldots,
αt=α0(0.55+0.45cos⁡(πt/50)),t=0,…,49.\alpha_t = \alpha_0(0.55 + 0.45\cos(\pi t/50)), \qquad t = 0,\ldots,49.

Proposition 2 For these initial centers and settings, independent uniform epoch shuffles make e-means return (0,80/3)(0,80/3) with probability 24/4924/49, and (5,29)(5,29) otherwise. Revival never triggers. Lloyd reaches (5,29)(5,29) in one pass.

Let the first three batches be (15,29,29,29)(15,29,29,29), (0,0,29,29)(0,0,29,29), and (0,0,29,29)(0,0,29,29). The right center stays at 29, while the left moves 15→2.637→0.90315 \to2.637 \to0.903. The crossing threshold is cL=1c_L = 1, since (1+29)/2=15(1 + 29)/2 = 15. Batch 3 contains no 15, yet moves the boundary to 14.951<1514.951 < 15 (Figure 2). When 15 returns, it goes right.

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.

Why the error persists. Once 0≤cL<10 \le c_L < 1 and 15≤cR≤2915 \le c_R \le29, only zeros go left. Every update preserves these bounds and keeps the midpoint below 15. At the end of training, e-means returns ordinary means of the assignments made during the final epoch [2 Algorithm 1]. These are (0,80/3)(0,80/3), which retain the worse partition. Thus after 25 passes,

Φe-means=4903≈163.33,ΦLloyd=150.\Phi_{\mathrm{e\text{-}means}} = \frac{490}{3} \approx163.33,\qquad\Phi_{\mathrm{Lloyd}} = 150.

an 8.89% increase over Lloyd’s one-pass loss. The returned centers have midpoint 40/3<1540/3 < 15, so they are also a Lloyd fixed point.

How often? Independently reshuffle the eight indexed observations each epoch. There are (84)=70\binom{8}{4}=70 possible first batches. Two disjoint events lead to the worse partition.

If batch 1 omits 15 and contains a zero, the boundary crosses 15 immediately. There are (74)−(54)=30\binom{7}{4}-\binom{5}{4}=30 such batches. Alternatively, batch 1 contains 15 and at most one zero, which occurs in (34)+2(52)=30\binom{3}{4}+2\binom{5}{2}=30 batches. In that case the boundary first crosses at batch 3 exactly when that batch contains both zeros and omits 15, as in the example above. There are (52)=10\binom{5}{2}=10 such first batches of epoch 2. The failure probability, conditional on the initial centers, is therefore

3070⏟3/7: first batch+30701070⏟3/49: third batch=2449.\underbrace{\frac{30}{70}}_{3/7:\ \text{first batch}}+\underbrace{\frac{30}{70}\frac{10}{70}}_{3/49:\ \text{third batch}}=\frac{24}{49}.

The first term reflects sensitivity to the first batch when the initial count is almost zero. The second is a later crossing after 15 has already been observed, isolating the forgetting mechanism illustrated above. Choosing two distinct data rows uniformly yields the prescribed pair of center values with probability 5/285/28.

Appendix A completes the proof of the exact probability by excluding later first crossings and revival.

All assignment and revival comparisons in this finite example are strict. Sufficiently small perturbations of the indexed observations and corresponding initial seed rows preserve its partition trajectories, with continuously varying losses.

Conclusion

Mass-based revival can destroy a global optimum and make e-means finish at a worse Lloyd fixed point. Under shared k-means++ seeding, the ratio of expected losses to Lloyd is still unbounded. A separate example isolates a later assignment change caused by forgetting. Both failures persist under small perturbations of the prescribed data and seeds. The constructions provide explicit tests of the published recipe in its acknowledged low-dimensional regime, and show why small usage alone cannot justify removing a center.

Certificate for Proposition 2

The exact probability uses a finite computation with outward-rounded interval arithmetic at 45 decimal digits, interpreting the printed coefficients as exact decimal constants. Here we specify the bounds being certified. Number updates by t=1,…,50t=1,\ldots,50, with at=αt−1a_t=\alpha_{t-1} and η=10−10\eta=10^{-10}. The retained initial mass and batch weights after update tt are

pt=η∏s=1t(1−as),wt,r=ar∏s=r+1t(1−as),1≤r≤t.p_t=\eta\prod_{s=1}^{t}(1-a_s),\qquad w_{t,r}=a_r\prod_{s=r+1}^{t}(1-a_s),\qquad1\le r\le t.

Let ur∈{0,1}u_r\in\{0,1\} indicate whether batch rr contains 15, and let zr∈{0,1,2}z_r\in\{0,1,2\} count its zeros. Before a first crossing, the right center is 29, and the left center satisfies

cL(t)15=pt+∑r=1twt,rurpt+∑r=1twt,r(ur+zr).\frac{c_L^{(t)}}{15}=\frac{p_t+\sum_{r=1}^{t}w_{t,r}u_r}{p_t+\sum_{r=1}^{t}w_{t,r}(u_r+z_r)}.

Each complete epoch contributes one 15 and two zeros. Pair the weights by epoch, assigning weight zero to an unseen second batch, and write

At=pt+∑(p,q)min⁡(p,q),A_t=p_t+\sum_{(p,q)}\min(p,q),
Zt−=2∑(p,q)min⁡(p,q),Zt+=2∑(p,q)max⁡(p,q).Z_t^-=2\sum_{(p,q)}\min(p,q),\qquad Z_t^+=2\sum_{(p,q)}\max(p,q).

Putting 15 in the lighter batch and both zeros in the heavier bounds any possible first crossing by

cL(t)≥15AtAt+Zt+>1.0275>1,t=4,…,50.c_L^{(t)}\ge\frac{15A_t}{A_t+Z_t^+}>1.0275>1,\qquad t=4,\ldots,50.

For the first three updates, direct evaluation for the possible pairs (u1,z1)(u_1,z_1), (u3,z3)(u_3,z_3), with (u2,z2)=(1−u1,2−z1)(u_2,z_2)=(1-u_1,2-z_1), gives exactly the two crossing events counted in § 3. Their respective counts among the 4900 equally likely indexed batch pairs are 2100 and 300; the other 2500 have no crossing.

To exclude revival, use a joint induction over the checks. Before a first crossing, updates keep 0≤cL≤150\le c_L\le15 and cR=29c_R=29; after a crossing, the invariant in § 3 gives 0≤cL<10\le c_L<1 and 15≤cR≤2915\le c_R\le29. In both cases zeros go left and copies of 29 go right. Assuming no earlier revival, the weight formulas therefore imply at each check

NLNL+NR=pt+Zt+2pt+4∑r=1twt,r>0.06410>0.05,t=5,10,…,50.\frac{N_L}{N_L+N_R}=\frac{p_t+Z_t^+}{2p_t+4\sum_{r=1}^{t}w_{t,r}}>0.06410>0.05,\qquad t=5,10,\ldots,50.

Every four-row batch contains at least one 29, so the right share is at least 1/4. Neither center is revived. This preserves the geometric conditions until the next check and closes the induction. The invariance argument in § 3 then determines the final partition from whether a crossing occurred.

The repository’s counterexamples.py verifies these bounds and the early-event classification using mpmath.iv, counts the 4900 indexed batch pairs, and reproduces the displayed center trace and losses against Lloyd.

References

  1. [1]David Arthur and Sergei Vassilvitskii. k-means++: The advantages of careful seeding. In Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 1027–1035, 2007. URL https://theory.stanford.edu/~sergei/papers/kMeansPP-soda.pdf.DOI
  2. [2]Swann Bessa, Pierre-Emmanuel Mazaré, Gergely Szilvasy, Hugo Touvron, David Picard, Matthijs Douze, and Hervé Jégou. e-means: Outperforming k-means (in one-tenth the epochs). arXiv preprint arXiv:2611.09501v1, 2026. URL https://arxiv.org/abs/2611.09501v1.
  3. [3]Loïc Cabannes. e-means: cost-based cluster revival. Faiss pull request #5915, November 12, 2026. URL https://github.com/facebookresearch/faiss/pull/5915.
  4. [4]Stuart P. Lloyd. Least squares quantization in PCM. IEEE Transactions on Information Theory, 28(2): 129–137, 1982. doi: 10.1109/TIT.1982.1056489.DOI
  5. [5]Avichal Sahai. e-means: dead-cluster revival overwrites real small clusters when k is small. Faiss issue #5907, November 12, 2026a. URL https://github.com/facebookresearch/faiss/issues/5907.
  6. [6]Avichal Sahai. e-means: opt-in revival policies that keep real small clusters. Faiss pull request #5908, November 12, 2026b. URL https://github.com/facebookresearch/faiss/pull/5908.

Paper details

vlnc:W_wmyawycx
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 9

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

Not recorded for this paper

View statement
Looking for related papers…
Contents