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).

Quality vs wall-clock

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.

The PISCES split

  • 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).

The two fish on real DEEP clusters Lemma 2 on real clusters

What PISCES changes

PISCES inside the e-means engine

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.

One PISCES batch as tensors

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%.

Where the time goes

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Γ—

Leave-one-out at full scale

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.

Scaling in k

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.

Downstream IVF at equal cost and the starved-cluster tail

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.

Downloads last month

-

Downloads are not tracked for this model. How to track
Inference Providers NEW
This model isn't deployed by any Inference Provider. πŸ™‹ Ask for provider support

Paper for Nabidnur/PISCES