Breaking 70 Years of Full-Batch Inertia with Mini-Batch Moving Averages
Deep learning transitioned to mini-batch optimization years ago, yet classical clustering has remained anchored to full-dataset scans for seven decades. The traditional Lloyd algorithm recalculates sample means across the entire dataset each round, rapidly exhausting time budgets on tens of millions of vectors. In November 2026, Matthijs Douze, Hervé Jégou, and fellow Faiss maintainers teamed up with researchers to introduce e-means. Originating from early exploratory work at Meta FAIR on mini-batch k-means, this new algorithm systematically injects modern deep learning optimization techniques into clustering tasks.
Since its introduction in 1957, Lloyd’s algorithm has dominated vector quantization and clustering. Each cluster tracks a sum vector $S_j$ and a count $N_j$, whose quotient defines the centroid coordinates. Before every update cycle, the algorithm must reset its accumulators and stream through the entire dataset. As centroids scale into the tens of thousands and sample sizes reach tens of millions, these repeated full-batch passes saturate memory bandwidth.
In 1967, academic research introduced MacQueen’s rule in an effort to enable streaming updates. MacQueen continuously accumulates statistics over incoming data without decaying historical weights. Consequently, data points erroneously assigned during early stages permanently contaminate centroid coordinates. Unable to purge early noise, cluster centers drift away from the true underlying distribution over time.
e-means addresses this fundamental flaw by replacing raw accumulation with an exponential moving average (EMA). Its update rule, formulated as $S_j \leftarrow (1-\alpha)S_j + \alpha s_j$, decays past assignments at rate $\alpha$. Centroids continuously track the local mean of recent batches, smoothly filtering out erroneous early assignments. While historically utilized in VQ-VAE codebook training, this mechanism delivers remarkably efficient convergence on static datasets as well.
Matching 25 Iterations of Error in Just 2 Epochs
Figure: Performance comparison between e-means and Lloyd across training epochs, CPU runtime, and GPU runtime. Source: e-means project page
Across 11 multimodal VIBE benchmark datasets, e-means exhibits remarkably rapid convergence. Tested vector dimensions span from 200 to 3,072, with cluster centroid counts set at 8,192 and 16,384. The new algorithm matches the test error of Lloyd running a full 25 iterations in just 1.6 to 2.4 epochs. Clustering workflows no longer require dozens of exhaustive iterations; two passes over the data are sufficient to approach global distribution geometry.
Historically, clustering optimizations traded accuracy for throughput—a compromise e-means completely dismantles. According to benchmark measurements on a single NVIDIA H100 GPU (bf16 precision), e-means reduces runtime by 10x to 45x compared to Flash-KMeans. Under CPU environments running against native Faiss implementations, it achieves an end-to-end speedup of 8x to 15x. Multiplied throughput and lower loss materialize concurrently within the same algorithmic framework.
Translating algorithmic epoch reductions into wall-clock advantages demands specialized low-level operator design. Under heavy workloads featuring 10 million vectors and 65,536 clusters, pure PyTorch Lloyd requires over 140 seconds, while Flash-KMeans clocks in between 14 and 22 seconds. e-means introduces dedicated fused kernels that combine nearest-centroid assignment with moving average updates into a single execution pass. Memory bandwidth overhead is drastically compressed, converting algorithmic efficiency directly into dozens of times in wall-clock speedups.
Figure: Convergence curves for training and test mean squared error relative to Lloyd iteration 25. Source: e-means project page
Inspecting training and test mean squared error (MSE) trajectories reveals distinctly divergent convergence dynamics. Lloyd descends sharply in early rounds thanks to full-batch averaging, but rapidly stalls into stagnation during intermediate and late phases. e-means matches Lloyd’s test error within just 1.5 epochs and steadily pushes test loss even lower in subsequent epochs. Upon completing training, the algorithm shifts centroids to the empirical mean of the final epoch, eliminating the slight lag introduced by exponential moving averages.
Mini-Batch Stochastic Noise Escapes Local Optima
Because clustering objective functions are fundamentally non-convex, deterministic optimization easily falls into dead ends. Every step of Lloyd’s algorithm strictly and monotonically reduces training MSE. This monotonic descent functions as a local trap: once centroids slide into a suboptimal basin of attraction, they can never escape. Suboptimal initial centroid placements become irrevocably locked in as final clustering outcomes.
Stochastic perturbations introduced by mini-batch sampling provide the necessary kinetic energy to explore the parameter landscape. Across 200 repeated training runs on synthetic benchmarks featuring two clusters of vastly disproportionate scale, Lloyd suffered a 26% failure rate by locking into local extrema. Under identical conditions, e-means suppressed the failure rate to just 3.5%. In collinear five-cluster topologies where Lloyd stalled with a 46% failure rate, e-means achieved a 0% failure rate.
The stochastic variance of batch sampling possesses an intrinsic capacity to traverse saddle points and overcome narrow energy barriers. Without relying on complex heuristic restarts, stochastic perturbations naturally reshape centroid trajectories. Just as stochastic noise acts as an exploration engine in deep networks, it demonstrates identical value in clustering tasks. Bypassing suboptimal local minima substantially elevates overall clustering quality.
To ensure stable convergence in later stages, step size scheduling adopts an annealing strategy. Using a cosine decay schedule, the learning rate gently cools from an initial $\alpha_0$ down to $0.1\alpha_0$. Larger initial step sizes facilitate aggressive exploration across cluster boundaries, while decayed step sizes in later stages lock in stability. Dynamic step sizes suppress stochastic oscillations, striking an optimal balance between broad exploration and pinpoint convergence accuracy.
Two Empirical Scaling Laws Eliminate Manual Tuning
Historically, mini-batch clustering struggled to displace Lloyd in production primarily due to hyperparameter tuning overhead. While Lloyd is computationally demanding, it requires virtually no parameter configuration beyond cluster count $k$ and iteration budget. In contrast, mini-batch mechanisms introduce tricky choices around batch size and learning rate. The time and compute spent on grid searches frequently wipe out any compute savings gained from individual runs.
Borrowing scaling law methodologies from deep learning, e-means solves the hyperparameter auto-tuning bottleneck. The authors fit two empirical formulas derived from sample size $n$, cluster count $k$, and compute budget $T$ to determine optimal hyperparameters. These closed-form expressions output batch size $B$ and initial step size $\alpha_0$ directly. On held-out test suites, the goodness of fit ($R^2$) for the two formulas reaches 0.96 and 0.95 respectively.
The real-world efficacy of these automated hyperparameters holds firm across diverse datasets. Compared to exhaustive grid searches, the median performance regret incurred by the empirical formulas ranges between just 0.06% and 0.20%. Engineers no longer need to spend compute budgets fine-tuning parameters—the algorithm autonomously selects optimal convergence trajectories. By eliminating hyperparameter search, this adaptive capability dramatically lowers the barrier to production deployment.
For high-precision quantization workloads, the research team also provides a quality-biased formulation variant. This configuration slightly moderates update pacing, trading modest throughput for even lower MSE. In large-scale vector index construction, these fractional loss reductions translate directly into improved retrieval recall. Engineering teams can flexibly toggle optimization modes based on their computational budgets and precision requirements.
Proportional Splitting Resurrects Thousands of Dead Centers
In industrial deployments, mini-batch clustering faces another notorious affliction: center starvation causing dead clusters. When certain centroids receive zero sample assignments in a given batch, their statistics drop to zero and updates grind to a halt. In high-cardinality codebooks ($k \ge 16384$), dead clusters drastically shrink effective codebook capacity. Numerous vacant centroids degrade quantization resolution and waste allocated compute.
Audio compression models like EnCodec handle dead clusters by randomly sampling instances from the current batch to populate empty slots. However, random replacement lacks topological grounding, causing reassigned centroids to quickly become marginalized again. Drawing on established Faiss engineering principles, e-means instead samples large clusters proportionally to their size and splits them in two. The algorithm directs surplus compute toward the densest sample manifolds, splitting along natural data contours.
Ablation benchmarks on the DEEP dataset highlight the dramatic performance divergence among resurrection strategies. In a 5-epoch run over 1 million vectors and 16,384 cluster centers, disabling resurrection produced 4,313 dead clusters (26.3% of the codebook) and a test MSE of 0.39448. EnCodec-style random resampling left 2,343 dead clusters with an MSE of 0.39124. Proportional splitting crushed dead clusters down to just 47 (0.3%), driving test MSE down further to 0.38762.
The same performance profile is confirmed on SIFT benchmarks, where proportional splitting slashes dead centroids from 2,080 down to 10. In vector quantization and audio compression pipelines, fully utilized codebooks govern signal fidelity. Resurrecting dead clusters converts previously idle compute bandwidth into tangible quantization precision.
e-means tears down the artificial barrier between classical clustering and deep learning optimization techniques. By synthesizing moving averages, cosine annealing, and cluster splitting into a unified framework, it breaks seven decades of algorithmic inertia in a fraction of the epochs. Delivering rapid convergence alongside superior quality, e-means propels large-scale vector quantization infrastructure into an entirely new evolutionary phase.
Reference Links:
- e-means Project Page and Interactive Demo
- arXiv Paper: e-means: k-means is fast and accurate with modern optimization
- Faiss Repository Contribution: contrib/e_means
- Hacker News Technical Discussion
