PISCES / README.md
Nabidnur's picture
PISCES (ARIES #1): code, paper, notebooks, results and figures
c09a3f4 verified
|
Raw History Blame Contribute Delete
13.6 kB
---
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).