--- license: mit library_name: faiss pipeline_tag: feature-extraction tags: - clustering - k-means - mini-batch-k-means - e-means - faiss - vector-search - vector-quantization - approximate-nearest-neighbor - unsupervised-learning - cpu --- # 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`](paper/pisces.pdf) · notebooks: [`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](https://arxiv.org/abs/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/`](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](figures/quality_vs_time.png) ## 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](figures/split_geometry.png) - **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](figures/split_real.png) ![Lemma 2 on real clusters](figures/mechanism.png) ## What PISCES changes ![PISCES inside the e-means engine](figures/architecture.png) 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](figures/tensor_flow.png) | 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](figures/time_breakdown.png) 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](figures/loo_bars.png) **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](figures/kscaling.png) **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](figures/ivf_and_sizes.png) ## 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`](notebooks/01_quickstart.ipynb) | PISCES vs e-means on a 200k-row DEEP slice | minutes, any CPU | | [`02_reproduce_kaggle_cpu.ipynb`](notebooks/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`](notebooks/03_results_analysis.ipynb) | every table and figure from the raw results, without training | seconds | ## Use it ```bash pip install -r requirements.txt python -m pytest -q tests # includes a bit-for-bit identity test against faiss e-means ``` ```python 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 ```bash 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`](docs/ABLATIONS.md) and [`results/dev/`](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 ```bibtex @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](https://arxiv.org/abs/2611.09501). Third-party data notices are in [`benchmarks/THIRD_PARTY.md`](benchmarks/THIRD_PARTY.md).