PISCES / docs /ABLATIONS.md
Nabidnur's picture
PISCES (ARIES #1): code, paper, notebooks, results and figures
c09a3f4 verified
|
Raw History Blame Contribute Delete
30 kB

Experiment log

Development rule: every design decision is made on DEEP* validation rows (the paper's validation half). Test rows are used only for reported results. SimSearchNet++ 1M and SPACEV 1M are held out: no PE-means variant is run on them until the design is frozen.

Proxy setting unless stated: DEEP* first 250k rows, k = 4,096 (same n/k β‰ˆ 61 as the paper's 1M / 16,384), batch law "throughput", seeds 1-5, matched starting rows, 4 threads. Numbers are paired % change in validation MSE vs official faiss e-means (negative = better). Raw rows: results/dev/<tag>.jsonl.

Iteration 0: PE-means v1 (full scale, test rows)

DEEP* 1M, k = 16,384, seeds 10-14: βˆ’0.31% / βˆ’0.27% / βˆ’0.20% at 1 / 3 / 5 epochs, 15/15 paired wins; PE at 3 epochs β‰ˆ official at 5 epochs (βˆ’0.01%) in 0.60Γ— the time. See README.

Iteration 1: which parts of the revival rule matter (iter1_knobs)

variant 1 epoch 3 epochs reading
PE-means v1 (offset 1, axis score, greedy, tau 0.1, every 5) βˆ’0.294% (5/5) βˆ’0.257% (5/5) reference
child offset Γ— 0.5 βˆ’0.242% βˆ’0.231% the Gaussian optimum (Γ— 1) is best, as Lemma 1 predicts
child offset Γ— 1.5 βˆ’0.292% βˆ’0.218%
donor score NΒ·trace instead of NΒ·Ξ»1 βˆ’0.173% βˆ’0.092% Lemma 2 confirmed: the top-axis gain is the right score
donor sampled ∝ gain instead of greedy βˆ’0.126% βˆ’0.146% greedy wins
tau 0.2 βˆ’0.230% βˆ’0.414% revive more aggressively helps at 3 epochs
tau 0.3 βˆ’0.033% βˆ’0.413% ... but hurts at 1 epoch
revival every batch βˆ’0.537% βˆ’0.298% frequent revival helps early
revival every 2 batches βˆ’0.430% βˆ’0.225%

Decision: keep offset 1, axis score, greedy. Revival should be more aggressive than e-means' default once splits are good, but a fixed tau trades early vs late. Hypothesis for iteration 2: a gain-vs-cost swap rule decides adaptively when to move a centroid.

Iteration 2: swap moves, consistent closing statistics (iter2_swap)

Hypotheses. (a) A streaming swap rule (move a live centroid when the best donor's split gain (2/Ο€)Β·NΒ·Ξ»1 exceeds the cluster's deletion cost Ξ£(d2 βˆ’ d1), estimated from 2-NN assignment) decides adaptively how aggressive revival should be. (b) faiss's closing means are built from last-epoch assignment sums; when a donor is split during that epoch, both children inherit the parent's pre-split sums. Splitting those statistics consistently (half count each, means at c Β± Ξ΄) should help most when the last epoch is the whole run.

variant 1 epoch 3 epochs time (3 ep.)
PE-means v1 βˆ’0.294% βˆ’0.257% 9.7 s
split_pass (consistent closing stats) βˆ’0.635% (5/5) βˆ’0.259% 9.9 s
swap 1% of k per check βˆ’0.223% βˆ’0.311% 11.4 s
swap 3% βˆ’0.135% βˆ’0.175% 11.7 s
every batch + swap 1% βˆ’0.092% +0.036% (1/5) 11.6 s
every batch + swap + split_pass βˆ’0.772% βˆ’0.253% 11.7 s
every batch + tau 0.2 βˆ’0.505% βˆ’0.348% 9.5 s
no revival in the last 5% of steps βˆ’0.295% βˆ’0.257% 9.7 s

Decision. Keep split_pass (it fixes a real inconsistency; doubles the gain at 1 epoch, never hurts, no cost). Drop swaps: inconsistent, +18% time, and harmful combined with frequent revival (negative result kept). Iteration 3 combines split_pass with faster revival and re-tunes the e-means scaling laws (LawFit) for the new revival rule.

Iteration 3: combinations and LawFit (iter3_combo_lawfit)

sp = split_pass. alpha Γ— s / batch Γ— s rescale the e-means fitted step / batch laws.

variant 1 epoch 3 epochs
PE-means v1 βˆ’0.294% βˆ’0.257%
sp βˆ’0.635% βˆ’0.259%
sp + every batch βˆ’0.825% βˆ’0.298%
sp + tau 0.2 βˆ’0.742% βˆ’0.419%
sp + every batch + tau 0.2 βˆ’0.960% βˆ’0.348%
sp + every 2 + tau 0.15 βˆ’0.801% βˆ’0.269%
sp + alpha Γ— 0.7 βˆ’0.540% βˆ’0.155%
sp + alpha Γ— 1.4 βˆ’0.729% βˆ’0.342%
sp + batch Γ— 0.5 βˆ’0.805% βˆ’0.219%
sp + batch Γ— 2 βˆ’0.582% βˆ’0.166%
official + batch Γ— 0.5 βˆ’0.255% βˆ’0.095%

Reading. With better revival, a larger EMA step helps at both budgets (the paper's step law was fitted with faiss revival), and revival should be more aggressive (tau 0.2). The fitted batch law is near-optimal at 3 epochs for both methods. Every-batch revival helps at 1 epoch only. Next: combine tau 0.2 with a larger step, and test a fresher closing window.

Iteration 4: combinations and closing window (iter4_combine)

variant 1 epoch 3 epochs
sp + tau 0.2 βˆ’0.742% βˆ’0.419%
sp + tau 0.25 βˆ’0.724% βˆ’0.361%
sp + tau 0.2 + alpha Γ— 1.4 (PE-means v2) βˆ’0.810% (5/5) βˆ’0.414% (5/5)
sp + tau 0.2 + alpha Γ— 2 βˆ’0.704% βˆ’0.184%
sp + every batch + tau 0.2 + alpha Γ— 1.4 βˆ’1.014% βˆ’0.308%
sp + closing window 0.5 +0.042% +0.696%
sp + closing window 0.75 βˆ’0.438% +0.035%
official + alpha Γ— 1.4 +0.068% +0.038%

Reading. A fresher closing window loses (more rows beat fresher rows): dropped. The larger step helps only PE-means, not official e-means, so the change is tied to the better revival rather than a flaw in the paper's step law. Finalists for full scale (DEEP\* 1M, k = 16,384, validation rows, fresh seeds 20-22): v2 = sp + tau 0.2 + alpha Γ— 1.4; sp + tau 0.2; and the 1-epoch specialist with every-batch revival.

Iteration 5: full-scale validation (DEEP* 1M, k = 16,384, validation rows)

Variants: pemeans = v1; pe_sp_tau0.2 = sp + tau 0.2; pe_v2 = sp + tau 0.2 + alpha Γ— 1.4; pe_e1_v2 = v2 + revival every batch. Two seed sets: 20-22 (results/deep1m_fullscale_val.jsonl) and 1-5 (running; the same variants are named F1/F2/F3 there). Report seeds 10-19 and the test rows stay unused until the design is frozen.

Seeds 20-22 (paired change vs official e-means):

variant 1 epoch 3 epochs seconds (3 ep.)
v1 βˆ’0.248% (3/3) βˆ’0.151% (3/3) 140
sp + tau 0.2 βˆ’0.700% (3/3) βˆ’0.196% (3/3) 152
v2 βˆ’0.701% (3/3) βˆ’0.264% (3/3) 144
v2 + every batch βˆ’0.933% (3/3) βˆ’0.256% (3/3) 168

Reading. v2 beats v1 at both budgets at no extra cost; the every-batch variant only pays off at one epoch and costs 17% more time at three. Full-scale gains at 3 epochs are smaller than on the proxy (βˆ’0.26% vs βˆ’0.41%).

Seeds 1-5 (same variants, named F1 = sp + tau 0.2, F2 = v2, F3 = v2 + every batch):

variant 1 epoch 3 epochs seconds (3 ep.)
v1 βˆ’0.162% (3/5) βˆ’0.218% (5/5) 146
F1 βˆ’0.573% (5/5) βˆ’0.166% (5/5) 143
F2 = v2 βˆ’0.618% (5/5) βˆ’0.214% (4/5) 145
F3 βˆ’0.833% (5/5) βˆ’0.162% (4/5) 147

Pooled over 8 seeds: v2 βˆ’0.65% / βˆ’0.23% at 1 / 3 epochs, v1 βˆ’0.19% / βˆ’0.19%.

Decision: freeze PE-means v2 (aries.pemeans.PE_V2: principal-axis gain-ranked revival, split_pass, tau 0.2, step law Γ— 1.4). It dominates v1 at equal cost. Confirmation (benchmarks/run_final_v2.sh): time-to-quality on validation rows, final DEEP* 1M test rows with report seeds 10-19, and the held-out SimSearchNet++ / SPACEV 1M datasets.

Iteration 6: new engineering and schedule ideas (iter6_v3_candidates, proxy)

variant (on top of v2) 1 epoch 3 epochs time (3 ep.)
v2 βˆ’0.810% βˆ’0.414% 10.4 s
child mass 0.35 / 0.25 of donor (vs 0.5) βˆ’0.807% / βˆ’0.813% βˆ’0.279% / βˆ’0.344%
tau cosine 0.3 β†’ 0.1 βˆ’0.703% βˆ’0.311%
revival every batch in the first 30% of steps (v3) βˆ’1.005% βˆ’0.405% 10.0 s
approximate assignment: IVF over centroids (64 cells, 8 probes), exact last epoch βˆ’0.810% βˆ’0.317% 7.6 s (official 8.6 s)

Child mass and tau schedules: negative, dropped. Early every-batch revival (v3) helps at 1 epoch. Approximate assignment is the first engineering win: faster than official e-means while better.

Iteration 7: approximate assignment across budgets (iter7_approx_budget, proxy)

run val MSE time
official 5 epochs 0.42937 13.3 s
v2 3 epochs 0.42867 9.5 s
v3 + approx 4 epochs 0.42831 11.0 s
v3 + approx 5 epochs 0.42837 12.6 s

At this proxy scale (k = 4,096) the assignment is a smaller share of cost, so approximate assignment helps but does not dominate; at k = 16,384 it should matter more (to be timed).

Iteration 8: graph-pruned assignment with label memory (iter8_graph, proxy) β€” negative

variant 3 epochs 5 epochs time (5 ep.)
v2 βˆ’0.414% βˆ’0.344% 15.6 s
v2 + graph (32 neighbours) +0.015% +0.324% 13.0 s
v2 + graph (64 neighbours) βˆ’0.035% βˆ’0.018% 17.0 s

Diagnosis: revival re-uses cluster indices, so a row's remembered label can point to a centroid that has been moved elsewhere; its candidate set is then the wrong neighbourhood. Fix for iteration 9: when an index is re-used, remap rows remembering it to the donor; and replace the NumPy gather/einsum candidate kernel (slower than BLAS) with a compiled (Numba) kernel.

Iteration 9: fixing graph-pruned assignment (iter9_graph_fixed, iter9b_graph_verified) β€” negative

Fixes: re-used cluster indices are remapped to the donor in every row's label memory; candidate distances run in a compiled Numba kernel (72x faster than faiss's full search for one full-scale batch, 0.020 s vs 1.44 s). Still worse: 64 neighbours βˆ’0.10% / +0.01% at 3 / 5 epochs (v2: βˆ’0.41% / βˆ’0.34%), though 35% faster. Diagnostic: one epoch after a row was last seen, 21% of rows have a nearer centroid outside the candidate set (assigned distance 8.6% too large): centroids move too much between visits under e-means' early large steps and revivals.

Self-verifying variant: each batch checks a random 1% of rows exactly and falls back to exact assignment when the mismatch exceeds 1% or 3%. Quality returns to v2's exactly, but the check fails on almost every batch, so it is only overhead (20 s vs 16 s at 5 epochs). Conclusion: label memory does not pay in this regime. Kernel and verification code are kept (aries/_kernels.py).

Iteration 10: approximate assignment at full scale (iter10_full_scale_approx)

DEEP* 1M, k = 16,384, validation rows, seeds 1-3. v3 = v2 + revival every batch in the first 30% of steps. apx LΓ—P = assignment through an IVF over the centroids with L coarse cells and P probes in every epoch but the last (exact); km = coarse cells from a 20-iteration k-means on the centroids, otherwise a random subset of centroids.

variant 3 epochs 4 epochs time 3 / 4 ep.
official e-means 0.38600 0.38611 115 / 147 s
v2 (exact) βˆ’0.112% (2/3) βˆ’0.216% (3/3) 130 / 170 s
v3 + apx 128Γ—16 βˆ’0.232% (3/3) βˆ’0.353% (3/3) 76 / 93 s
v3 + apx 128Γ—16 km βˆ’0.305% (3/3) βˆ’0.277% (3/3) 75 / 93 s
v3 + apx 128Γ—32 km βˆ’0.119% (2/3) βˆ’0.201% (3/3) 96 / 121 s

Reading. At full scale the assignment dominates the cost, so approximate assignment makes PE-means 35-37% faster than official e-means at equal epochs while winning every seed. More probes (more exact) is consistently worse: the approximation appears to help, like annealing noise. Iteration 11 isolates this (v3 exact vs 8 / 16 probes, 5 seeds).

Iteration 11: is the approximation itself helping? (iter10_11_full_scale_approx)

DEEP* 1M, k = 16,384, validation rows, 5 seeds (32 probes: 3 seeds), 3 epochs.

variant vs official wins time
official e-means 0.38634 β€” 113 s
v3, exact assignment βˆ’0.173% 4/5 129 s
v3 + apx 128Γ—8 km βˆ’0.209% 4/5 68 s
v3 + apx 128Γ—16 km βˆ’0.340% 5/5 75 s
v3 + apx 128Γ—16 (random cells) βˆ’0.319% 5/5 76 s
v3 + apx 128Γ—32 km βˆ’0.119% 2/3 96 s

Reading. There is a clear sweet spot: exact assignment is worse than moderately approximate assignment (16 probes), and 8 probes is too noisy. Approximate early-epoch assignment acts like annealing noise and also removes 42% of the time. Rule that transfers across k: √k coarse cells from a short k-means on the centroids, √k / 8 probes, exact final epoch.

Decision: freeze PE-means v3 (aries.pemeans.PE_V3). Confirmation (run_final_v3.sh): time-to-quality (val), DEEP* 1M test rows seeds 10-19, held-out SimSearchNet++ / SPACEV 1M.

Confirmation of the frozen PE-means v3 (run_final_v3.sh)

Time to quality (validation rows, seeds 1-5; results/deep1m_v3_time_to_quality_val_summary.md):

run val MSE vs official at 5 epochs time ratio
official 3 epochs 0.38634 +0.198% 0.59Γ—
official 5 epochs 0.38558 β€” 1.00Γ— (222 s)
v3 2 epochs 0.38625 +0.174% 0.27Γ—
v3 3 epochs 0.38503 βˆ’0.143% (4/5) 0.33Γ—
v3 4 epochs 0.38494 βˆ’0.164% (5/5) 0.42Γ—

DEEP* 1M test rows, report seeds 10-19 (results/deep1m_cpu_summary.md):

epochs v3 vs official 95% CI wins Wilcoxon p time
1 βˆ’0.963% [βˆ’1.042, βˆ’0.870] 10/10 0.002 43 vs 42 s
3 βˆ’0.279% [βˆ’0.355, βˆ’0.205] 10/10 0.002 66 vs 114 s
5 βˆ’0.215% [βˆ’0.270, βˆ’0.152] 9/10 0.004 99 vs 199 s
v3 3 ep. vs official 5 ep. βˆ’0.111% [βˆ’0.184, βˆ’0.032] 8/10 0.34Γ—

Held-out datasets (never used in development; 3 epochs, seeds 10-14):

dataset v3 vs official 95% CI wins time
SPACEV 1M βˆ’0.444% [βˆ’0.512, βˆ’0.380] 5/5 68 vs 103 s
SimSearchNet++ 1M βˆ’0.032% [βˆ’0.038, βˆ’0.025] 5/5 178 vs 252 s

Verdict for algorithm 1: PE-means v3 is better than official e-means at every budget on every dataset tested, by up to ~1% at one epoch, and reaches e-means' 5-epoch quality in about a third of the time. The quality margin is small on SimSearchNet++; the speed margin holds everywhere.

Iteration 12: fairness ablation and approximate last epoch (full scale, val, seeds 1-3, 3 epochs)

variant vs official wins time
v3 (exact last epoch) βˆ’0.305% 3/3 75 s
official e-means + the same approximate assignment +0.128% 1/3 66 s
official e-means + approximate assignment incl. last epoch (64 probes) +0.128% 1/3 73 s
v3 + approximate last epoch, 32 probes βˆ’0.304% 3/3 53 s
v3 + approximate last epoch, 64 probes βˆ’0.305% 3/3 73 s

Reading. Approximate assignment does not improve e-means by itself (it makes it 0.13% worse); its benefit appears only together with principal-axis revival. Against e-means given the same speed-up, PISCES is ~0.43% better. An approximate last epoch with √k/4 probes is a free 30% speed-up.

Iteration 13: coarse-to-fine growth (iter13_growth, proxy) β€” negative

Start with k/2^g centroids, double g times by splitting every cluster along its principal axis (0.5 epoch in total), then train at k.

variant 1 epoch 3 epochs
PISCES, no growth βˆ’1.005% βˆ’0.425%
growth g = 2 / 3 / 4 +1.011% / +1.043% / +1.022% βˆ’0.133% / βˆ’0.166% / βˆ’0.148%

Splitting every cluster regardless of its gain, from under-trained coarse codebooks, loses to random-row starts plus gain-ranked revival. Dropped.

Iteration 14: cell-batched GEMM assignment (kernel benchmark, one full-scale batch)

Profile of a 3-epoch PISCES run: 78% of time in faiss's IVF search (scalar per-query scans). Two BLAS reformulations: (a) query-centric candidate sets, one product per cell: identical results, same speed (0.71 vs 0.70 s); (b) cell-centric candidate sets shared by all rows of a cell: 1.6x faster at 16-32 probes but recall drops (0.874-0.933 vs 0.983-0.996), and iteration 11 showed lower recall costs quality. Kept faiss IVF; kernels kept in aries/_kernels.py.

Decision: freeze PISCES = v3 + approximate last epoch (√k/4 probes): aries.pemeans.PISCES.

Final confirmation: PISCES (run_final_pisces.sh)

PISCES = v3 + approximate last epoch (√k/4 probes). All numbers in paper/macros.tex, generated by paper/make_data.py from the raw rows.

evaluation PISCES vs official e-means wins time ratio
DEEP* 1M test, 1 epoch βˆ’0.88% 10/10 0.68Γ—
DEEP* 1M test, 3 epochs βˆ’0.28% 10/10 0.49Γ—
DEEP* 1M test, 5 epochs βˆ’0.22% 9/10 0.43Γ—
PISCES 3 ep. vs official 5 ep. (test) βˆ’0.11% 8/10 0.28Γ—
PISCES 3 / 4 ep. vs official 5 ep. (val) βˆ’0.14% / βˆ’0.16% 4/5, 5/5 0.24Γ— / 0.33Γ—
SPACEV 1M held-out, 3 epochs βˆ’0.44% 5/5 0.60Γ—
SimSearchNet++ 1M held-out, 3 epochs βˆ’0.045% 5/5 0.70Γ—
e-means + same sparse assignment, DEEP test / SPACEV / SimSearchNet++ +0.07% / +0.11% / +0.03% 3/10, 0/5, 0/5 0.64Γ— / 0.72Γ— / 0.80Γ—
PISCES vs e-means + same sparse assignment (DEEP test, 3 ep.) βˆ’0.35% 10/10

Per-seed: PISCES is better than official e-means on 39 of 40 runs.

Iterations 15-19: after freezing PISCES, six new ideas (proxy: DEEP 250k, k = 4,096, val rows, seeds 1-5)

Profile first: 76% of a 3-epoch PISCES run is faiss's IVF search, 5% the axis statistics (reduceat), 5% the e-means np.add.at sums. Every candidate is a switch in PEmeans.

Iteration 15 (iter15_candidates): heavy-ball momentum on centroid moves, fewer probes early, closing Lloyd polish.

variant 1 epoch 3 epochs time (3 ep.)
PISCES βˆ’0.943% βˆ’0.425% 6.5 s
momentum 0.3 / 0.6 (first 70% of steps) βˆ’0.837% / βˆ’0.024% βˆ’0.141% / +0.220% 6.0 s
probes 4β†’16 / 8β†’16 over the early epochs (same: 1 epoch is all last epoch) βˆ’0.350% / βˆ’0.329% 6.2 s
+ closing Lloyd polish (exact or 16 probes) βˆ’1.362% βˆ’0.471% 8.1 s

Momentum and probe schedules: negative. Polish: one Lloyd step after training (re-assign every row to the closing means, recompute the means). It helps most at 1 epoch, where the closing means include rows assigned against the starting rows.

Iteration 16 (iter16_polish_short, iter16_pisces_long): is the polish better than spending the same time on more epochs? Absolute val MSE / seconds:

budget PISCES PISCES + polish (8 probes)
1 epoch 0.43256 / 2.3 s 0.43066 / 3.4 s
1.5 epochs 0.43107 / 3.8 s
2 epochs 0.42940 / 4.7 s 0.42899 / 5.7 s
2.5 epochs 0.42907 / 5.3 s
3 epochs 0.42862 / 6.5 s 0.42838 / 7.6 s

At 1 epoch the polish beats 50% more training (better and faster); at 2-3 epochs it is on the time-quality front of plain PISCES (no worse, not clearly better). A second, label-memory polish step (each row checked only against the 32 centroids nearest its previous centroid, Numba kernel) adds βˆ’0.1% at 1 epoch; the label memory is too stale for the first step (73% of labels survive the closing means at 1 epoch, 9% of true nearest centroids fall outside the candidate set).

Iteration 17 (iter17_hnsw): HNSW over the centroids instead of IVF. Microbenchmark on one full-scale batch (65,536 rows, k = 16,384): IVF 16 probes 1.0 s at recall 0.996; HNSW (M 16, ef 32) 0.18 s build + 0.34 s search at recall 0.995; vectors can be overwritten in place between rebuilds. But on the proxy it is slower (k = 4,096) and worse: βˆ’0.31% to βˆ’0.36% at 3 epochs vs βˆ’0.43%, and higher recall is worse still. Negative.

Iteration 18 (iter18_fp16_polish): fp16 IVF lists (same recall, ~30% faster scans in the microbenchmark): βˆ’0.29% vs βˆ’0.43% at 3 epochs. Negative, like HNSW: the particular errors of float32 IVF with √k/8 probes are part of why PISCES works (iteration 11), and other approximations do not reproduce them. A cheaper last epoch (√k/8 probes) to pay for the polish: βˆ’0.32%, negative.

Iteration 19 (iter19_anneal): explicit annealed assignment, a fraction Ξ΅(t) of rows (decaying linearly to 0 at 70% or 30% of training) sent to the runner-up centroid, on top of the polish. Ξ΅0 = 0.01 / 0.03 / 0.10: βˆ’0.461% / βˆ’0.397% / βˆ’0.361% at 3 epochs vs βˆ’0.481% without. Negative.

Decision: carry PISCES + polish (√k/8 probes) to full-scale validation; drop the rest.

Iteration 20: polish at full scale; cheaper polish; global split-merge audit

Full-scale polish (DEEP* 1M, k = 16,384, val rows, seeds 1-5; results/deep1m_polish_time_to_quality_val.jsonl). PISCES + one closing Lloyd step (√k/8 probes) vs PISCES at the same number of epochs: βˆ’0.37% / βˆ’0.11% / βˆ’0.05% / βˆ’0.02% at 1 / 2 / 3 / 4 epochs, 5/5 seeds each. A timing check in the same session (results/dev/iter20_timing_check.jsonl) shows the machine ran ~20% slower than when the PISCES / official time-to-quality rows were recorded (official 3 ep. 155 s vs 131 s, PISCES 65 s vs 54 s; the PISCES / official ratio is stable, 0.42 vs 0.41), so absolute seconds are only compared within a session. Corrected for that, the polished runs sit on PISCES' own time-quality curve: the polish buys about what the same time spent on more epochs buys.

Cheaper polish (label memory, full scale, seed 1): after 3 epochs 96.5% of the training labels are still the exact nearest centroid, and the nearest centroid of the polished codebook is among the 32 centroids nearest the row's previous centroid for 98.9% of rows. Three label-memory Lloyd steps (Numba candidate kernel, 32 candidates) take 5.3 s and give βˆ’0.047%; at 1 epoch they give βˆ’0.33% in 5.7 s (labels are staler there: 72% survive). Again on the time-quality curve, not beyond it.

Global split-merge audit (proxy, 3 seeds, swap_proto): after PISCES, with exact 2-NN deletion costs and power-iteration split gains, only 8-10 of 4,096 clusters admit a split-merge move whose predicted gain exceeds its cost; applying them changes val MSE by βˆ’0.015% beyond the same number of Lloyd steps. PISCES' revival already leaves a codebook that is close to swap-optimal (the mechanism analysis compares this count with official e-means at full scale).

Decision: PISCES is unchanged. The closing polish is kept as an option (polish=1) for users who compare at a fixed number of passes; it is not part of the method.

Iteration 21: distribution-free splits, batch-size schedule, child mass (iter21_halfmean_batch, proxy)

Lemma 1 assumes Gaussian clusters. Two distribution-free alternatives, tracked online at the same O(Bd) cost: (a) the exact half-mean split, children at c Β± E[sign(p) e] and donor score Nβ€–E[sign(p) e]β€–Β² (one exact 2-means step of the hyperplane split, for any symmetric distribution); (b) the empirical axis half-mean, children at c Β± E|p|Β·u and score N(E|p|)Β².

variant 1 epoch 3 epochs
PISCES (Gaussian closed form √(2λ₁/Ο€), score (2/Ο€)Nλ₁) βˆ’0.943% βˆ’0.425%
half-mean split + half-mean score βˆ’0.288% βˆ’0.120%
E|p| split + E|p| score βˆ’0.877% βˆ’0.417%
half-mean split, Gaussian score βˆ’0.688% βˆ’0.360%
Gaussian split, E|p| score βˆ’0.874% βˆ’0.334%
batch size 0.5B β†’ 1.5B (linear in rows, step ∝ B^0.9) βˆ’0.863% βˆ’0.434%
batch size 0.25B β†’ 1.75B βˆ’0.877% βˆ’0.324%
children keep 70% of the donor's mass βˆ’1.017% βˆ’0.417%

The Gaussian closed form wins: it uses only the second moment along the axis, which the EMA power iteration estimates with low variance, while the first-moment estimates mix sign flips of a still-moving axis. Batch schedules and child mass: no reliable gain. PISCES' algorithm stays as it is.

Iteration 22: engineering β€” fused statistics kernel and 8-bit scans with exact re-rank

Profile: 76% of a run is faiss's IVF search, ~22% is NumPy bookkeeping (np.add.at sums, reduceat axis statistics, residual gathers, sorts).

  • Fused kernel (fused=True): one parallel Numba pass over the batch, rows sorted by label, computes e-means' sums and counts and PISCES' Ξ£(eΒ·u)e and Ξ£(eΒ·u)Β² together. Same quantities (unit test against NumPy); only the summation order differs. Full scale: identical splits and val MSE, 66.0 β†’ 49.6 s and 61.9 β†’ 52.4 s (seeds 1-2).
  • Rejected engineering (same session, one 65,536-row batch, k = 16,384): sorting queries by coarse cell (identical results, no speed-up: the scan is compute-bound, not cache-bound); GEMM per IVF list with a thread pool (identical results, 0.94-1.16 s vs faiss 0.82-0.97 s). The machine runs dense distance computations at 25-30 GFLOPS and faiss's scan already reaches that.
  • 8-bit scans with exact re-rank (codec="sq8r"): IVF lists stored as 8-bit scalar-quantized codes, the best 4 candidates re-ranked with exact float32 distances. Agreement with the float32 IVF result: 100.000% on the benchmark batch (99.988% with 2 candidates); search 0.68 β†’ 0.53 s at 16 probes.

Full scale, val rows, 3 epochs, 5 seeds, same session (results/dev/iter22_fused_sq8r_full_val.jsonl):

configuration val MSE vs official 5 ep. time
PISCES v1.0 0.38502 βˆ’0.145% ~64 s (same-session timing check)
+ fused kernel 0.38502 βˆ’0.144% 46.8 s
+ fused kernel + 8-bit scan / exact re-rank 0.38514 βˆ’0.114% 40.1 s

With 8-bit scans, 3 of 5 seeds are identical to float32 (same splits, same MSE); on 2 a rare tie-break difference sends training down a different trajectory (+0.137%, +0.012%), which is seed-level noise. Decision: final PISCES = PISCES v1.0 + fused kernel + 8-bit scans with exact re-rank (aries.pemeans.PISCES; the previous configuration is PISCES_V10). Same algorithm, about 1.6Γ— faster. Final confirmation: benchmarks/run_final.sh β†’ results/final/.

Iteration 23: the 8-bit scan needs d % 8 == 0 (found on held-out SPACEV)

The first held-out SPACEV run (results/final/superseded/spacev1m_test_unpadded_scan.jsonl) had the best quality gain of all three datasets (βˆ’0.46%, 5/5 seeds), but PISCES took ~350 s against ~130 s for e-means, while e-means with the same IVF (float32 lists) took ~70 s. Cause: faiss' SIMD 8-bit scalar-quantizer scan is only used when d is a multiple of 8. SPACEV has d = 100 (DEEP 96, SSNPP 256), so the scan fell back to a scalar loop. Micro-benchmark, 1 thread, 16,384 centroids, 8,192 rows, 16 of 128 probes: d = 100 β†’ 3.10 s, d = 104 β†’ 0.36 s, d = 96 β†’ 0.24 s.

Fix (engineering, no algorithmic change): zero-pad centroids and rows to the next multiple of 8 for the scan and the re-rank. Padded coordinates contribute exactly 0 and the per-dimension 8-bit codes of the real coordinates are unchanged; the SIMD kernel sums in a different order, so float rounding can flip a rare near-tie (unit test test_sq8r_assignment_any_dimension: >99.9% of labels equal to float32 IVF at d = 96 and d = 100). As in iteration 22, one flipped tie sends a run down a different trajectory, so SPACEV MSEs are not bit-identical to the first run (seed 10: 7164.42 β†’ 7162.05) but within seed noise. SPACEV was re-run with the fix in the same session as the other follow-ups (results/final/spacev1m_test.jsonl); seed 10 time: 457 s β†’ 45 s (e-means 116 s).

Iteration 23b: sparse assignment does not pay at small k (iter23_small_k_val)

The scaling study (results/final/scaling_k1024_val.jsonl) showed PISCES 1.80Γ— slower than e-means at k = 1,024. Same session, DEEP* 1M, k = 1,024, val rows, 3 epochs, seeds 1-3, paired vs official:

configuration change vs e-means seeds won time
PISCES (sparse assignment, √k = 32 cells, 4 probes) βˆ’0.059% 2/3 1.93Γ—
PISCES v1.0 βˆ’0.060% 2/3 2.68Γ—
PISCES with exact assignment (fused kernel kept) βˆ’0.078% 2/3 0.83Γ—

At k = 1,024 the exact GEMM is cheap (official takes ~9 s) and building the IVF index every batch costs more than it saves. Decision: the "auto" sparse-assignment rule now applies only from APPROX_MIN_K = 4,096 on; below it PISCES uses exact assignment. This changes nothing at k β‰₯ 4,096 (every test-row, held-out and analysis result). The threshold was chosen from these validation runs, so the k = 1,024 result with the rule is not a held-out number.

Iteration 24: early revival needs informative counts (iter24_k65536_regime_val)

At k = 65,536 and n = 1M the quality gain nearly vanished (βˆ’0.04%, 1/3 seeds; results/final/scaling_k65536_val.jsonl) while PISCES re-seeded 114k clusters against 48k for e-means. With B = 65,536 a cluster sees about one row per batch, a Poisson count with relative standard deviation 1. Same data, k = 65,536, val rows, 3 epochs, seeds 1-3, paired vs the official runs of the scaling study:

variant per seed mean revivals
PISCES βˆ’0.302 / +0.099 / +0.074 βˆ’0.043% 114,496
Ο„ = 0.1 βˆ’0.118 / +0.026 / +0.132 +0.013% 90,002
no early revival βˆ’0.369 / βˆ’0.056 / βˆ’0.143 βˆ’0.190% (3/3) 79,950
Ο„ = 0.1, no early revival βˆ’0.305 / βˆ’0.021 / +0.213 βˆ’0.038% 65,210

Fewer revivals alone is not the answer (Ο„ = 0.1 with no early revival revives least and is not better); what hurts is the every-batch phase acting on one-row counts. Decision: early every-batch revival applies only when the batch holds at least EARLY_MIN_ROWS = 2 expected rows per cluster (B β‰₯ 2k); otherwise PISCES revives every 5 batches like e-means. Every reported run at k ≀ 16,384 has B/k β‰₯ 2 (the 1-epoch runs sit exactly at 2), so the rule changes only k = 65,536. It was chosen on these validation runs, so the k = 65,536 number with the rule is not a held-out result.