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.