File size: 13,633 Bytes
c09a3f4 | 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 | ---
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*).

## 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`](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).
|