PISCES: principal-axis splitting makes mini-batch k-means faster and better than e-means
ARIES #1 (Aryan's Iterative Efficiency Series) Β· technical report: paper/pisces.pdf Β·
notebooks: notebooks/
PISCES stands for Principal-axis Informed Splitting with Consistent closing, Early revival and Sparse
assignment. It is a drop-in improvement on e-means (Bessa et al., Meta FAIR, 2026,
arXiv:2611.09501), the state-of-the-art mini-batch k-means that ships in
faiss.contrib.e_means. We test it on e-means' own benchmark and compare against e-means' own code. Every
comparison below is paired by seed and timed in a single session on one 4-core CPU, and every number is generated
from the raw per-run files in results/final/.
| DEEP* 1M, k = 16,384, the paper's test rows, 10 seeds | change in test MSE vs e-means | 95% CI | seeds won | wall-clock |
|---|---|---|---|---|
| 1 epoch | β0.88% | [β0.94, β0.82] | 10/10 | 0.42Γ |
| 3 epochs | β0.27% | [β0.35, β0.19] | 10/10 | 0.30Γ |
| 5 epochs | β0.28% | [β0.32, β0.23] | 10/10 | 0.27Γ |
| PISCES at 3 epochs vs e-means at 5 epochs | β0.10% | 9/10 | 0.17Γ | |
| held-out SPACEV 1M (3 epochs, never used in development) | β0.453% | 5/5 | 0.37Γ | |
| held-out SimSearchNet++ 1M (3 epochs) | β0.040% | 5/5 | 0.34Γ | |
| e-means given PISCES' sparse assignment (fairness check) | +0.07% | 3/10 | 0.59Γ |
At e-means' own benchmark setting (k = 16,384), PISCES has lower error than e-means on all 40 paired runs (3 datasets, 1-5 epochs), at 0.27-0.42Γ its wall-clock. When e-means gets the same fast assignment, its error goes up (worse on 17 of 20 runs), so PISCES' advantage is not borrowed engineering. The gain depends on k: it peaks around k = 16,384; at k = 65,536 the frozen settings gain almost nothing and the released defaults recover β0.19% with a rule chosen on validation runs (see Scaling in k).
The two fish
When a cluster dies, e-means revives it by copying a donor centroid with a 10β»β΄ relative nudge. The two copies then start on top of each other. PISCES instead places the two children where an optimal 2-means split of the donor would put them. They sit at c Β± β(2Ξ»β/Ο) Β· uβ, symmetric along the donor's principal axis, like two fish swimming in opposite directions.
- Lemma 1 (half-Gaussian children). Cutting a Gaussian cluster by the hyperplane through c orthogonal to an eigenvector u gives halves with means c Β± β(2Ξ»/Ο)Β·u.
- Lemma 2 (distortion removed by a split). That split removes (2/Ο)Β·NΒ·uα΅Ξ£Β²u / uα΅Ξ£u β€ (2/Ο)Β·NΒ·Ξ»β of squared error, with equality on the top eigenvector. So the best donor is the cluster with the largest NΒ·Ξ»β, not the most populated one.
- Both quantities are tracked online by an EMA power iteration, at O(Bd) cost per batch.
On 400 real DEEP clusters, the prediction of Lemma 2 tracks the gain actually achieved by the split: median realized/predicted 1.17, log-log correlation 0.947. The principal-axis split removes a median 1.05Γ as much distortion as an unrestricted 2-means with five restarts. As a donor score, the Gaussian closed form also beat two distribution-free estimates that we built to replace it (iteration 21).
What PISCES changes
One batch as tensors (PlotNeuralNet styles): the grey block is the full B Γ k distance tensor exact e-means computes; PISCES computes only the teal slab, about k/8 wide.
| component | kind | what it does |
|---|---|---|
| principal-axis split | mathematical | children at c Β± β(2Ξ»β/Ο)Β·uβ (Lemma 1) |
| gain-ranked donor | mathematical | donor = argmax NΒ·Ξ»β (Lemma 2) |
| streaming power iteration | algorithmic | each cluster's axis is tracked from EMA statistics, one power-iteration step per batch |
| consistent closing statistics | algorithmic | a split in the last epoch also splits the donor's closing sums |
| early revival + re-fitted step | algorithmic | revival every batch in the first 30% of steps, threshold 0.2, step law Γ 1.4 |
| sparse assignment | algorithmic + engineering | IVF over the centroids: βk cells, βk/8 probes (βk/4 in the last epoch) |
| fused statistics kernel | engineering | one parallel Numba pass computes e-means' sums and PISCES' axis statistics |
| 8-bit scans with exact re-rank | engineering | 8-bit IVF scans, with the best 4 candidates re-ranked in float32. This returns the float32 answer for 100.000% of rows on a full-scale batch |
The last two engineering changes leave the algorithm itself unchanged. On the 10 report seeds, they take PISCES to 0.74Γ the time of PISCES v1.0 (the version without them), with a paired quality difference of +0.012%.
Profiled in one session (DEEP* 1M, k = 16,384, 3 epochs): e-means takes 75 s, 96% of it in the exact assignment search. PISCES takes 27 s. Its sparse search is still 89% of its time, so assignment remains the cost to attack next.
Analysis
Every component, removed one at a time, at full scale (validation rows, 3 epochs, 3 seeds; cost is relative to PISCES, positive = worse):
| removed | change vs e-means | removal costs | time |
|---|---|---|---|
| nothing (PISCES) | β0.258% | 0.31Γ | |
| principal-axis split | β0.019% | +0.240% | 0.30Γ |
| gain-ranked donor | +0.114% | +0.373% | 0.30Γ |
| consistent closing | β0.248% | +0.010% | 0.30Γ |
| threshold 0.2 β 0.1 | β0.105% | +0.154% | 0.31Γ |
| step Γ 1.4 β Γ 1.0 | β0.163% | +0.096% | 0.31Γ |
| early revival | β0.117% | +0.141% | 0.31Γ |
| sparse last epoch (exact instead) | β0.253% | +0.005% | 0.49Γ |
| sparse assignment (exact everywhere) | β0.023% | +0.236% | 1.00Γ |
Scaling in k (n = 1M, validation rows, 3 epochs). There are two regimes, and we report both:
| k | rows per cluster | PISCES as frozen | time | released defaults | time |
|---|---|---|---|---|---|
| 1,024 | ~1,000 | β0.06% (2/3) | 1.80Γ | β0.08% (2/3) | 0.83Γ |
| 4,096 | ~250 | β0.22% (3/3) | 0.42Γ | same | same |
| 16,384 | ~60 | β0.31% (5/5) | 0.30Γ | same | same |
| 65,536 | ~15 | β0.04% (1/3) | 0.27Γ | β0.19% (3/3) | 0.26Γ |
The speed-up grows with k, as the cost model predicts. PISCES as frozen for the main benchmark had two weak ends, and the released defaults add one rule for each:
- k = 1,024: the exact search is cheap, so building a sparse index every batch does not pay. Below k = 4,096 PISCES now assigns exactly (iteration 23b).
- k = 65,536: a cluster sees about one row per batch, so its EMA count is too noisy for every-batch revival. Fewer revivals alone does not help (threshold 0.1: +0.01%); dropping the every-batch phase does. It is now on only when a batch has at least 2 rows per cluster (iteration 24).
Both thresholds were chosen on these validation runs, so those two cells are not held-out results. Neither rule changes any other number on this page.
Downstream: the centroids as an IVF index (10K DEEP1B queries, exact ground truth; this is the job e-means is built for). The two indexes are equally good: at equal search cost, the PISCES index' recall@1 differs by β0.02 points on average (range β1.29 to +0.78), and reaching recall@1 = 0.9 takes 0.99Γ the distance computations. The list-imbalance factor is 1.194 for PISCES and 1.187 for e-means. So downstream, PISCES gives the same index in a fraction of the training time, not a better index. The codebooks differ in the starved tail: e-means leaves 0.19% of its clusters with fewer than 10 rows, PISCES 0.00%.
Mechanism. PISCES re-seeds 14,426 clusters in a 3-epoch run, against 6,982 for e-means, almost all in the first 30% of training. Afterwards we audited both codebooks for global split-merge moves that would still pay off. The e-means codebook admits 282 of them, the PISCES codebook 45. PISCES does during training what a post-hoc split-merge search would do afterwards.
Honest rating
Scored by the author's own standard: what would a careful reviewer at a top venue say?
| criterion | score | why |
|---|---|---|
| beats the newest state of the art on its own benchmark | 8/10 | Better than official e-means on all 40 paired runs at k = 16,384 (two held-out datasets included) and 2.4-3.7Γ faster. Outside that regime the frozen method needed two post-hoc rules, which are not held-out results |
| size of the quality gain | 6/10 | β0.88% at 1 epoch, shrinking to β0.28% at 5 epochs. These are real and consistent, but small in absolute terms, as is typical once a clusterer is near convergence |
| speed | 9/10 | 0.30Γ the time at 3 epochs; e-means' 5-epoch quality in 0.17Γ its time; 0.27Γ at k = 65,536; 0.83Γ at k = 1,024 with the small-k rule |
| rigor | 9/10 | Official baseline code; fingerprint-checked data; development on validation rows only; held-out datasets; a fairness baseline; full-scale leave-one-out; 24 logged iterations with every negative result, including the regimes where PISCES does not help |
| novelty | 6/10 | Principal-direction splits are classical (LBG, PDDP, G-means). What is new is the streaming estimator, gain-ranked revival inside e-means, the consistent closing and the finding that sparse assignment helps only together with them |
| theory | 6/10 | Two exact lemmas, checked on real clusters. Why approximate assignment helps is still a hypothesis |
| reproducibility | 10/10 | CPU only, one script per table, raw results and data fingerprints included |
| overall | 7.7/10 | A solid, honest improvement on a 2026 state-of-the-art method in the regime it was built for (tens to hundreds of rows per cluster). Not a new paradigm |
Notebooks
| notebook | what it does | time |
|---|---|---|
01_quickstart.ipynb |
PISCES vs e-means on a 200k-row DEEP slice | minutes, any CPU |
02_reproduce_kaggle_cpu.ipynb |
the paper's protocol on a free Kaggle CPU notebook | about 30 min for 5 seeds |
03_results_analysis.ipynb |
every table and figure from the raw results, without training | seconds |
Use it
pip install -r requirements.txt
python -m pytest -q tests # includes a bit-for-bit identity test against faiss e-means
import numpy as np
from aries import pisces
x = np.load("train.npy").astype("float32") # (n, d)
centroids, model, _ = pisces(x, k=16384, nepochs=3, seed=0)
aries.PEmeans subclasses faiss's NumpyEmeans. With every PISCES option switched off, it reproduces
official e-means bit for bit.
Reproduce everything
python benchmarks/get_deep1m.py DATA/deep1b # DEEP* 1M with SHA-256 fingerprint checks
python benchmarks/get_paper1m.py DATA # SPACEV 1M and SimSearchNet++ 1M with the paper's held-out rows
bash benchmarks/run_final.sh DATA 4 # every number in the report, about six hours on 4 cores
python paper/make_data.py && (cd paper && pdflatex pisces.tex && pdflatex pisces.tex)
The development history (24 iterations, every run) is in docs/ABLATIONS.md and
results/dev/.
Differences from the e-means paper's setup, stated up front:
- assignment runs in CPU float32 (the paper used an H100 in bfloat16);
- the shared starting rows are drawn with NumPy instead of CUDA.
Limitations
- The gains are largest at small budgets, and the quality gap shrinks as both methods converge.
- The quality gain depends on rows per cluster: it is largest around 60 (k = 16,384 at n = 1M). At about 15 rows per cluster (k = 65,536) the frozen PISCES gains nothing. The released default recovers β0.19% there, but that rule was chosen on the same validation runs.
- Two regime rules (exact assignment below k = 4,096; every-batch revival only when B β₯ 2k) were set on validation runs after the main evaluation.
- The gain on SimSearchNet++ 1M is small (β0.040%).
- The optimality arguments assume roughly Gaussian clusters. They hold well on DEEP, but other data may differ.
- We tested only CPU; we did not benchmark a GPU implementation.
Citation
@techreport{aryan2026pisces,
title = {{PISCES}: Principal-Axis Splitting Makes Mini-Batch k-Means Faster and Better than e-means},
author = {Aryan},
institution = {ARIES: Aryan's Iterative Efficiency Series},
number = {1},
year = {2026}
}
PISCES builds on e-means and its open-source implementation in faiss (MIT). Please also cite
arXiv:2611.09501. Third-party data notices are in
benchmarks/THIRD_PARTY.md.









