torann · branch query-batched-join · 2026-07-27

What the index is actually being asked to do

One open question answered, one new wall found. Recall has a floor rather than a price — and above d≈8 the force law consuming those neighbours stops being able to tell them apart, which changes the problem.

0.45%

CE cost of halving recall at d=32, empty start — the slack the index can spend

17%

CE cost of losing all true neighbours, though substitutes are only 5% further away

86%

how hard the 64th neighbour pushes relative to the 1st at d=32 — the force law cannot discriminate

93.2%

ceiling on L^0.5 recall from the L1 hash, at any retrieval width

Baselines, and the trap underneath them

ESS imports the installed torann, not the repository. Every number here was taken after rebuilding and reinstalling the wheel, with the installed .so hash checked against the one built from this branch. An earlier session lost an hour to measuring a 12-day-old build twice.

The standing sweep, 48 configurations, reported per epoch: brute 359.8 ms/epoch geometric mean (82% of it query), LSH 16.25 ms/epoch (55% query). One sweep run was discarded and repeated because another job overlapped ~90 s of it.

The six ESS shapes, batched join vs per-query

Every shape's trajectory fingerprint matched — results are bit-identical across the two paths.

d	shape	L	per-query	batched	speed-up	recall
2	0+256	—	0.17s	0.14s	n/a	exact
2	256+512	4	0.24s	0.21s	1.14×	1.000
8	0+1024	8	0.48s	0.39s	1.24×	0.991
8	1024+2048	8	1.18s	0.85s	1.38×	1.000
32	0+10000	24	17.65s	12.75s	1.38×	0.689
32	10000+20000	24	101.12s	64.82s	1.56×	0.861
all	six shapes		120.83s	79.16s	1.53×	query 1.65×

Does ESS need recall, or only plausible repellers?

The evidence was ambiguous because it confounded two things: cutting LSH tables degrades recall and locality together. This separates them. The index is exact throughout, so recall is imposed rather than measured — the neighbour list is corrupted between the query and the force kernel, and the true toroidal-L1 distance of every substituted point is passed through, so only the selection changes and force magnitudes are never confounded with it.

Answer

Recall has a floor, not a price. Half the true neighbours can go almost free — 0.45% CE at d=32, 0.29% from the filled start — but losing all of them collapses the result to the uniform null, even when the substitutes are only 5% further away. A distance ranking is the product. Redesigning the index around cost per plausible local neighbour is ruled out.

The filled start — anchors that cannot be pushed, which is the case ESS is actually for — is uniformly less sensitive (10.4% at recall 0 against 17.2% empty), so the slack measured from an empty start is a lower bound on the slack in production.

at or above the uniform null below it — actively clustered uniform null

The full record

d = 32 · empty start · 0+4000

arm	recall	mean ratio	Clark-Evans	vs exact	separation	epochs
exact	1.000	1.00	1.2074 ±0.0015	—	6.0752	151
top2k	0.500	1.00	1.2019 ±0.0021	-0.45%	5.9403	126
rank1-4k	0.000	1.05	0.9993 ±0.0014	-17.24%	3.6295	110
rank8-16k	0.000	1.16	0.9830 ±0.0039	-18.59%	3.6741	117
ratio2x	0.001	1.45	1.0008 ±0.0003	-17.11%	3.9632	40
uniform	0.001	1.45	1.0008 ±0.0003	-17.11%	3.9695	40

d = 32 · filled start · 2000+4000

arm	recall	mean ratio	Clark-Evans	vs exact	separation	epochs
exact	1.000	1.00	1.1427 ±0.0021	—	4.1058	118
top2k	0.500	1.00	1.1394 ±0.0024	-0.29%	4.1058	112
rank1-4k	0.000	1.04	1.0236 ±0.0008	-10.42%	3.4952	118
rank8-16k	0.000	1.14	1.0075 ±0.0020	-11.83%	3.6029	114
ratio2x	0.001	1.45	1.0227 ±0.0003	-10.50%	3.6974	27
uniform	0.001	1.45	1.0227 ±0.0003	-10.50%	3.6974	27

d = 8 · empty start · 0+2048

arm	recall	mean ratio	Clark-Evans	vs exact	separation	epochs
exact	1.000	0.99	1.4741 ±0.0063	—	0.9058	166
top2k	0.500	0.99	1.4183 ±0.0176	-3.78%	0.7703	131
rank1-4k	0.000	1.12	0.8253 ±0.0210	-44.01%	0.0251	171
rank8-16k	0.000	1.46	0.9440 ±0.0049	-35.96%	0.1833	151
ratio2x	0.009	1.71	1.0083 ±0.0029	-31.60%	0.2981	38
uniform	0.002	2.28	1.0042 ±0.0019	-31.88%	0.2959	27

d = 8 · filled start · 1024+2048

arm	recall	mean ratio	Clark-Evans	vs exact	separation	epochs
exact	1.000	0.98	1.3375 ±0.0056	—	0.3291	110
top2k	0.500	0.99	1.3040 ±0.0041	-2.51%	0.3291	106
rank1-4k	0.000	1.12	0.9591 ±0.0206	-28.29%	0.0526	128
rank8-16k	0.000	1.43	1.0098 ±0.0052	-24.50%	0.2033	125
ratio2x	0.008	1.72	1.0459 ±0.0083	-21.81%	0.2371	53
uniform	0.002	2.39	1.0379 ±0.0054	-22.40%	0.2395	51

The new wall: above d≈8 the force law stops discriminating

Everything above treats the index's job as "return the true k nearest". This is about the fact that the thing consuming those neighbours can no longer tell them apart. Measured on ESS-converged points with the Gaussian law esa defaults to:

share of the vote from ranks 1–8

d	rank 1 weight	rank 8	rank 64	share from ranks 1–8
2	0.1586	0.02083	3.66e-27	99.95%
8	0.1235	0.1024	0.0193	23.58%
32	0.349	0.3296	0.299	13.27%

At d=32 the 64th neighbour pushes 86% as hard as the nearest, because all 64 distances lie in [6.13, 6.31] — a 3% spread. Three consequences:

Magnitude carries almost no information at high d. The entire signal is which points come back; a wrongly-returned far neighbour votes at nearly full strength. That is the mechanism behind the collapse above.

Radius mode cannot work at d=32 either, since "inside R" stops being a distinction. Related: at convergence zero neighbours lie inside R at any shape tested — the nearest sits at 1.15–1.4·R, because ESS pushes to equilibrium just outside the interaction radius.

ESS destroys its own contrast as it converges. Relative spread at d=32 is 24.2% on uniform points against 2.9% on converged ones — making points equidistant is precisely its job. Any benchmark on random data measures an easier problem than the real one.

Cells sized from the force law: exact at d≤4, impossible at d≥8

Look in the query's own cell plus the face-adjacent ones — von Neumann, 1+2d cells; the L1 ball makes diagonal cells pointless. That needs capture (width w ≥ R, since L∞ ≤ L1) and selectivity (occupancy n/B^d small) simultaneously. They cross between d=4 and d=8.

d	n	R	cells/dim allowed (capture)	needed (occupancy)	1+2d	verdict
2	512	0.0442	22.63	10.12	5	works
4	2048	0.1956	5.11	4.50	9	works
8	2048	0.7355	1.36	2.12	17	impossible
16	2048	2.2118	0.45	1.46	33	impossible
32	10000	5.1095	0.20	1.27	65	impossible
64	2048	12.4236	0.08	1.10	129	impossible

At d≥16 the capturing cell is larger than the whole domain. This is the same wall as the measured geometry elsewhere, now in the force law's own terms — and it is why a ring-search engine stays scoped to d≤4.

Lower p restores contrast — about two octaves of dimension

Relative spread (r₆₄−r₁)/r₁ on ESS-converged points. p=0.25 at d=32 beats L1 at d=16, and approaches L1 at d=8.

p = 1.0p = 0.5p = 0.25

The required force sharpness relaxes with it — σ/r₁ for 10:1 discrimination goes from 0.113 at p=1 to 0.309 at p=0.25 — so the two fixes reinforce rather than compete. A power law is not the route: reaching the same 10:1 needs r⁻⁸¹ at d=32 and r⁻¹³³ at d=64.

But the L1 hash cannot retrieve L^p neighbours

The grid hash collides with probability 1 − B·δ per sampled dimension, so log P(collide) ~ −B·Σδⱼ — a function of L1 and nothing else. Two points with equal L1 and very different L^0.5 are retrieved with equal probability, so ranking its candidates by L^p reranks a set that was never selected for it.

Measured against the real LSH at d=32, n=4000. The dashed line is the plateau: it is not retrieval width, it is the hash's own L1 recall (0.689 here). The missing ~7% never collide, so no rerank at any width reaches them.

The mitigating fact is that the L^p-nearest are not far in L1 — median L1 rank 18, 90th percentile 55, max 147 — and the refine kernel already scores ~4118 candidates per query, so the rerank itself costs one vsqrtps per lane plus a bigger heap, not extra retrieval. But do not ship it as an L^p index. The cap is structural.

The tuner optimises a target nobody chose

_tune sets L = ceil(log(0.10) / log(1 − p1)), clamped to [4, 24]. That 0.10 is a hardcoded 90% collision target for a true k-NN — a recall objective never derived from what ESS needs. Query is 68–85% of ESS wall time and L drives probe count linearly:

per-table collision p1	L for 90% (current)	for 69% (delivered)	for 50%
0.05	45	23	14
0.10	22	12	7

The contradiction worth resolving first

Imposed recall 0.5 costs 0.45% CE. But cutting tables to L=12 costs 4.3% and L=8 costs 7.3%. Those cannot both describe "less recall", so cutting tables must be doing something else.

Two candidates, both testable in ~20 minutes: misses are replaced by far points rather than omitted (the −18% regime), or low recall flattens the force EMA and fires the early-stop prematurely, so the loss is a convergence artifact. The ablation's epoch counts favour the second — corrupted arms stopped at 40 epochs against 151 for exact. The measurement: run at L=24 and L=8 and record the true rank of every returned neighbour.

What is missing is not a knob — num_tables, resolution, dims_per_table, target_bucket_size, probes, query_block_size and brute_threshold all override the tuner — but an objective: no way to say "I need recall 0.5, not 0.9".

Ruled out this session

condition	d	p	mean k-occurrence	max	skew
uniform	8	1.0	5.0	13	+0.32
ESS-converged	8	1.0	5.0	15	+0.47
uniform	32	1.0	5.0	14	+0.36
ESS-converged	32	1.0	5.0	13	+0.40
ESS-converged	32	0.5	5.0	14	+0.37

Hubness. No runaway hubs anywhere — skew +0.32…+0.47 with a maximum k-occurrence of 13–15 against a mean of 5, for uniform and converged points, at both dimensions, under p=1 and p=0.5. So hubness-corrected metrics (mutual proximity, local scaling) are not a lead.

A power-law force. r⁻⁸¹ at d=32 for 10:1 discrimination. The Gaussian's r² in the exponent is what makes the same job reachable.

The original "within 2× the k-th distance" arm. At d=32 it agrees with uniform random to four decimals on every column — the ball has swallowed the whole point set. Replaced by rank-window arms that pin recall at zero while varying locality independently.

What is next

A hash family designed natively for p < 1. The target is per-dimension collision ~exp(−c·δ^p). The lever is randomising the cell width: E_w[max(0, 1−δ/w)] represents any convex decreasing f, and exp(−c·δ^p) is convex for p<1. The obstacle is toroidal — the wrap needs w = 1/B with integer B, capping the mixing distribution at w=0.5 instead of a continuum. That is theory to settle before code. The bar to beat is the 93.2% rerank ceiling; below it, the construction has bought nothing.

A sharper force law (σ 0.5 → ~0.11 at d=32) is the other half of the fix and belongs to ESS, not to the index.

Not yet measured. ESS is a refinement method — called repeatedly, each call handed the points it produced before — so the filled start is the normal case and the static tier grows without bound. Every benchmark here measures a single call, and each call re-fits the index and re-tunes (B,K,L) from scratch. bench_refine_rounds.py is written for exactly this and has never been run. Separately, there is no FAISS comparison on the ESS workload at all — the existing scripts use uniform random data at k=2·D — so "competitive with FAISS on ESS" should be treated as unestablished.