|
Download README.md from Nabidnur/PISCES: direct link, hf CLI and curl.
- Browser
- Download file 13.6 kB
-
https://huggingface.co/Nabidnur/PISCES/resolve/main/README.md
- Command line
-
hf download hf://Nabidnur/PISCES/README.md
-
curl -L -o README.md https://huggingface.co/Nabidnur/PISCES/resolve/main/README.md
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*). | |
|  | |
| ## 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). | |