File size: 29,952 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 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312 313 314 315 316 317 318 319 320 321 322 323 324 325 326 327 328 329 330 331 332 333 334 335 336 337 338 339 340 341 342 343 344 345 346 347 348 349 350 351 352 353 354 355 356 357 358 359 360 361 362 363 364 365 366 367 368 369 370 371 372 373 374 375 376 377 378 379 380 381 382 383 384 385 386 387 388 389 390 391 392 393 394 395 396 397 398 399 400 401 402 403 404 405 406 407 408 409 410 411 412 413 414 415 416 417 418 419 420 421 422 423 424 425 426 427 428 429 430 431 432 433 434 435 436 437 438 439 440 441 442 443 444 445 446 447 448 449 450 451 452 453 454 455 456 457 458 459 460 461 462 463 464 465 466 467 468 469 470 471 472 473 474 475 476 477 478 479 480 481 482 483 484 485 486 487 488 489 490 491 492 493 494 495 496 497 498 499 500 501 502 503 504 505 506 507 | # 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.
|