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

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