Recall cliff (up to 65pp) on sparse data at weak-block dims (dim = 8·odd or 16·odd)

[RyanCodrai]

Found by bug-hunt wave 11 (recall-quality lens). Severity: high for sparse/bag-of-words workloads; dense embeddings unaffected.

turbovec/src/rotation.rs:92: block_size(dim) is the largest power-of-two divisor of dim, and the Walsh-Hadamard mixes only within B-sized blocks (2 rounds, rotation.rs:30-48). When B is 8 or 16, the transform cannot Gaussianize inputs that actually need mixing — and recall falls off a cliff between adjacent dims.

Recipe: n=20,000, 10-nonzero random sparse (N(0,1) values), L2-normalized, 300 held-out queries, seeds 0 and 1. Metric matches benchmarks/suite/recall_*.py (control: real openai-1536 n=100k 2-bit → R@1 0.886 vs published 0.891; GloVe d=200 4-bit → 0.840 vs 0.8498).

dim	B	bits	R@1 (s0 / s1)	R10@10
1024	1024	2	0.883 / 0.850	0.919 / 0.915
1016	8	2	0.453 / 0.427	0.557 / 0.547
1032	8	2	0.393 / 0.410	0.533 / 0.553
1040	16	2	0.780 / 0.760	0.839 / 0.833
1088	64	2	0.883 / 0.860	0.923 / 0.918
2048	2048	2	0.913 / 0.917	0.942 / 0.944
2056	8	2	0.270 / 0.263	0.453 / 0.449

Monotone recovery in B, reproducible across seeds, and the gap widens with dim (−47pp at 1032, −65pp at 2056). Present at 4-bit too (d=2048 R@1 0.990 vs d=2056 0.707). Also reproduced on a tf-idf-like recipe (nz=20, |N(0,1)|): d=1024 0.847 vs d=1032 0.483 at 2-bit.

Scope: dense real embeddings are fine — openai-1536 truncated to 1528/1032/520/264 (all B=8) and nytimes-256→248 all matched their power-of-2 neighbours within ±1.5pp. This bites sparse / bag-of-words / SPLADE-style / hashed-feature vectors — exactly what the rotation exists for.

Undocumented: rotation.rs internally acknowledges "weak-block dims (B = 8)", but no user-facing doc (README, docs/api.md) warns that dim choice affects recall. Someone picking dim 1000, 1032, 2056 or 3000 with sparse features silently loses half their recall; padding to 1024/1088 fixes it. At minimum this needs a doc warning; better would be a constructor warning or more mixing rounds when B is small.

🤖 Generated with Claude Code

[github-actions]

Claude finished @RyanCodrai's task in 55s —— View job

---

Triage

Kind: Bug report — a recall-quality defect (with a secondary documentation gap). Not a crash or correctness bug in the code path itself: the rotation behaves exactly as designed, but the design under-mixes at certain dimensions, and nothing warns users about it.

What's going on: The quantizer relies on a deterministic block-Hadamard rotation to make every coordinate look Gaussian before encoding. The block size B is the largest power-of-two divisor of dim (block_size, turbovec/src/rotation.rs:92), and the Walsh-Hadamard only mixes within B-sized blocks over K = 2 rounds (rotation.rs:69). For dims like 1032 (8·129) or 2056 (8·257), B collapses to 8, so each coordinate is only ever combined with a handful of others — too little mixing to Gaussianize sparse inputs. The module's own comments (rotation.rs:48-55) acknowledge "weak-block dims (B = 8)" as a known soft spot, but the reported measurements (down to R@1 0.26 at dim 2056 vs 0.91 at 2048) show the effect is far larger on sparse data than anything the docs or tests cover. Note K and the rotation seed are frozen v5 wire-format constants, so a fix that adds mixing rounds would be a format change — the cheap immediate remedies are a doc warning and/or a constructor warning suggesting padding to a friendlier dim.

Most relevant files:

• turbovec/src/rotation.rs — the rotation itself: block_size (line 92), K = 2 rounds (line 69), and the module docs describing the weak-block behavior
• turbovec/tests/recall_sanity.rs — recall regression tests (currently don't cover sparse data at weak-block dims)
• README.md (Recall / How it works sections) and docs/api.md — user-facing docs with no warning that dim choice affects recall
• turbovec/src/lib.rs — TurboQuantIndex construction, where a runtime warning for weak-block dims would live

Summary

turbovec compresses vectors so that similarity search uses far less memory, and a key step is a "shuffle" (a rotation) applied to every vector before compression so that its values end up in a predictable, bell-curve-like shape the compressor is tuned for. This issue reports that the shuffle's strength depends on the vector dimension you choose: for most sizes it mixes values across the whole vector, but for sizes like 1000, 1032, or 2056 it only mixes small groups of 8 values at a time. Ordinary dense embeddings (like those from OpenAI models) don't mind, but sparse vectors — ones that are mostly zeros, common in keyword or bag-of-words setups — don't get mixed enough, and search accuracy collapses: in the reporter's tests, the fraction of correct top results dropped from about 91% at dimension 2048 to about 27% at dimension 2056, even though those sizes differ by only 8.

The reporter shows the effect is consistent across random seeds, grows with vector size, and disappears entirely if you pad the vectors to a "friendly" dimension like 1024 or 1088. Nothing in the user-facing documentation warns about this, so someone could pick an unlucky dimension and silently lose half their accuracy. The suggested fixes, from cheapest to most thorough: document which dimensions are safe, warn at index creation time, or strengthen the mixing for the weak sizes — though the last one would change the stored data format, which the code intentionally keeps frozen.

[RyanCodrai]

Root-caused, and a fix is prototyped and measured. A follow-up agent patched Rotation::new/apply_with_scratch in a throwaway copy to make the round count settable, then re-ran identical workloads.

It's a round-count failure, not a block-size failure. After K globally-permuted B-block Hadamard rounds, each output coordinate depends on at most B^K inputs. At B=8, K=2 that's 64 of 1032/2056 coordinates — the transform never becomes a full mixer. The rule predicting every measurement: mixing is complete iff B^K ≥ dim.

recall@10, bits=2, n=5000:

dim	B	data	K=2	K=3	K=4	K=6
2048	2048	sp16	0.924	0.920	0.927	0.917
2056	8	sp16	0.585	0.895	0.925	0.927
1032	8	sp16	0.690	0.884	0.899	0.898
776	8	sp8	0.724	0.921	0.930	0.940
2056	8	sp4	0.735	0.914	0.967	0.970

K=4 lands within noise of the corresponding power-of-two dim everywhere; K=6 adds nothing. No block-decomposition change is needed — no mixed-radix, no internal padding, no different permutation (perms already differ per round; the limiter is fan-in). Intermediate sizes behave exactly as B^K ≥ dim predicts: B=16 loses ~2pp, B=64+ loses nothing.

Cost of K=4 (20k vectors, 4-bit): encode 101.999 → 105.754 ms at dim 2056 (+3.7%), 91.7 → 95.3 ms at dim 1536 (+3.9%); search unchanged (query rotation is negligible).

Suggested one-line fix at rotation.rs:69: K = min k ≥ 2 such that block_size(dim)^k ≥ dim. Gated per-dim, this leaves 768/1024/1536/2048/3072 at K=2 — wire format unchanged for every common dim — and only re-formats the dims that are currently broken.

---

It is not a synthetic-sparse artifact. All-dense, all-nonzero realistic structure is hit as hard (recall@10, bits=2, K=2):

data	dim 2048	dim 2056	delta	2056 @ K=4
power-law decay (matryoshka/MRL, PCA-projected)	0.906	0.668	−23.8pp	0.892
4 dominant coords + dense noise	0.947	0.748	−19.9pp	0.940
8 coords at 10× energy	0.848	0.761	−8.7pp	0.849
i.i.d. gaussian	0.562	0.563	0	0.565
clustered (32 centers)	0.319	0.320	0	0.317
concatenated 2-model	0.644	0.663	0	0.654
duplicated coordinate pairs	0.670	0.669	0	0.671

Power-law / importance-ordered embeddings are the worst-hit realistic case (−23.8pp) — the exact family the rotation.rs:41-55 doc comment says the leading permutation handles. The permutation removes the ordering dependence but not the concentration dependence, so the doc's "two rounds are statistically indistinguishable from the old QR rotation's recall" holds only when B^2 ≥ dim and should be scoped. Encouragingly, concatenated multi-model and duplicated-dim data are not hazards — the leading global permutation genuinely defuses those.

And it compounds with the frozen calibration (#285/#317):

dim	B	power-law fresh	power-law frozen	freeze cost
1024	1024	0.879	0.875	−0.4pp
2048	2048	0.906	0.905	−0.1pp
1032	8	0.721	0.532	−18.9pp
2056	8	0.668	0.438	−23.0pp

2048-fresh → 2056-frozen is −46.8pp. Mechanism is coherent: unmixed coordinates keep heavy per-coordinate-idiosyncratic marginals, so a mis-fitted (shift, scale) has something to be badly wrong about; after full mixing every coordinate is near-Gaussian and the freeze barely matters. The K=4 build removes the compounding entirely — 2056 power-law frozen goes 0.438 → 0.896. So fixing the rotation also de-fangs #285/#317 at these dims.

[RyanCodrai]

⚠️ This finding is now DISPUTED — a second independent agent could not reproduce the recall cliff. Flagging rather than burying it, because the first result looked strong and this one directly contradicts it.

The verification agent implemented the exact gated form (K = min k ≥ 2 with block_size(dim)^k ≥ dim) and confirmed the mechanism works: Rotation gains a k field, apply_with_scratch already loops 0..K so it generalizes free, and apply_scaled_into's fused 2-round schedule stays byte-for-byte intact with extra rounds appended. Verified by FNV-1a over to_bytes(), n=2000: 768/1024/1536/2048/3072 → identical hashes and byte lengths (all keep k=2); 1032/2056/200 → different hashes, same lengths (k=4, 4, 3). All 20 Rust suites pass.

But the recall claim did not hold up. Their harness (n=20k, 200 queries, exact cosine top-10 ground truth, tight 10-member clusters, coordinate-energy gradient over 4 regimes including matryoshka-style truncation):

regime	1024 (k=2)	1032 before → after	2048 (k=2)	2056 before → after
isotropic	1.000	1.000 → 1.000	1.000	1.000 → 1.000
decay e^-3	0.844	0.924 → 0.922	1.000	0.996 → 0.996
decay e^-8	0.244	0.319 → 0.318	0.649	0.658 → 0.656
head=64 (MRL)	0.064	0.136 → 0.134	0.072	0.057 → 0.058

Weak-block dims came out consistently as good as or better than their power-of-two neighbours, and K=4 moved recall by at most −0.002 (noise, and always slightly negative).

So one of the two harnesses is wrong, and I can't tell you which from here. The original measured a 65pp gap on 10-nonzero sparse data and a 23.8pp gap on power-law dense data with clean monotone recovery in B and reproducibility across two seeds; this one measured nothing on four regimes including a power-law sweep. The data recipes differ (sparse-with-10-nonzeros and PCA-projected power-law vs clustered/decay/MRL-truncated), so the honest reading is that the cliff may be real but confined to a narrower data family than the first report implied. Worth resolving with a real dataset before spending format-compatibility risk on it.

Two things from the verification that are worth keeping regardless of how this resolves:

1. rotation_determinism's golden-byte tests have no coverage at 8·odd dims. A K change there would silently invalidate every existing on-disk index at those dims and CI would not notice. That's a real coverage hole independent of this issue (companion to Test-coverage holes found by mutation testing: codebook support bound, NEON tail clamp, FLUSH_EVERY loop, 3-bit accuracy #307).
2. The proposed formula can yield an odd k (dim 200 → k=3), which breaks apply_with_scratch's "even K ends in row" invariant and needs a final copy-back — cheap, but a real edge the current const-assert guards.

Cost where it applies: add time at 1032/2056 rises ~5–15%; k=2 dims unaffected (768: 70.1 → 71.0 ms).

[RyanCodrai]

✅ DISPUTE RESOLVED — the cliff is real, and the null result was a measurement artifact. But the practical exposure is narrower than the original report implied.

A third agent adjudicated with a validated harness (reproduced the published recall_d1536_2bit.json pipeline first: recall@1 0.903 vs published 0.891, @2 0.987 vs 0.979, @4 0.999 vs 0.998 — small positive drift because the wheel is newer than the pinned result, see #312).

The mechanism is confirmed by direct measurement, not inference. Probe: zero coordinate j, set it to δ, count changed code bytes in to_bytes():

dim	δ=0.002	0.01	0.05	0.2
1024	11	34	124	377
1032	2	8	31	65 (saturated)
2048	11	53	253	752
2056	4	13	33	127 (saturated)

At 8·odd dims the affected set caps at ~64 coordinates regardless of δ; at power-of-two dims it keeps growing toward full dim. B^K = 8² = 64, confirmed empirically.

Recall reproduces the original almost exactly (recall@10, exact-cosine ground truth, 2 seeds):

data	bits	n	1024	1032	2048	2056
sp10	2	5000	0.929	0.688	0.950	0.651
sp10	2	20000	0.915	0.538	0.943	0.456
sp16	2	20000	0.885	0.538	0.919	0.424
sp16	4	20000	0.960	0.886	0.973	0.832

(Original claimed sp16/2-bit/n=5000: 0.924 vs 0.585; this run gets 0.925 vs 0.594. Seed spread ≤0.005.) The gap widens with n and roughly halves at 4 bits.

Why the verification agent measured nothing — every one of its four regimes is insensitive by construction: isotropic sits at recall 1.000 (no headroom); its decay e^-3 / e^-8 regimes genuinely are near-null (independently measured here at −0.6pp and −1.8pp — far too mild, the effect needs i^-1-class concentration); head=64 MRL sits at 0.06–0.14 (floor, all noise); and n=20k with only 200 queries gives ±0.03 standard error, hiding anything under ~5pp. Its other work — the mechanism verification, byte-hash checks, the golden-bytes coverage hole at 8·odd dims, and the odd-k invariant issue — all stands.

The boundary, and it matters for prioritization. Dense energy-concentrated data at 2-bit, n=5000:

data	2048	2056	delta
power-law i^-1	0.905	0.566	−33.9pp
power-law i^-0.5	0.871	0.757	−11.4pp
4 dominant coords ×10	0.786	0.689	−9.7pp
exp decay e^-3	0.726	0.720	−0.6pp

Real data is the tiebreaker: OpenAI-3072 PCA-projected to 2048 vs 2056, n=20k, 1000 queries — 2-bit 0.913 vs 0.910, 4-bit 0.969 vs 0.969. No gap.

So: the cliff is real and large, gated on per-vector energy concentrated in ≲64 coordinates' worth of mass — random sparse (bag-of-words/SPLADE-like) and steep power-law spectra. It does not appear on i.i.d. dense, mildly-decaying, or real OpenAI embeddings raw or projected. That argues for documenting/warning rather than treating it as a general recall regression, with the per-dim gated K bump reserved for the sparse/lexical users who need it.

[RyanCodrai]

⚠️ Scope escalation: "dense data is safe" is wrong. The earlier adjudication concluded the cliff was confined to sparse/lexical and steep power-law data. A consolidated recall measurement found dense anisotropic data loses 13–17 pp at 2-bit at the same weak-block dims:

data	2-bit	4-bit
dense anisotropic, d=2048 → 2056	0.870 → 0.697 (−17.3 pp)	0.949 → 0.915 (−3.4 pp)
dense anisotropic, d=1024 → 1032	−13.3 pp	—
10-nz sparse, d=1024 → 1032	0.926 → 0.546 (−37.9 pp); R@1 0.873 → 0.373 (−50.0 pp)	0.971 → 0.900 (−2.5 pp)

Real openai truncated to 1032 still shows no cliff (0.845 vs 0.852 at d=1024), so real dense embeddings remain safe — but "dense ⇒ safe" is the wrong rule to document. The correct rule is about per-coordinate energy concentration, which anisotropic dense data has plenty of.

This is now the single largest recall lever in the codebase, measured against every other known degradation source on one scale (R10@10, same base config):

rank	source	cost
1	weak-block dim, sparse, 2-bit	−37.9 pp (R@1 −50.0)
2	quantization floor, 2-bit	−18.3 pp (irreducible)
3	weak-block dim, dense anisotropic, 2-bit	−17.3 pp
4	quantization floor, 4-bit	−7.4 pp (irreducible)
5	weak-block dim, 4-bit	−2.5 to −3.4 pp
6	7-bit query LUT (#332)	1.5–3.5 pp @4-bit (cited)
7	calibration identity/warm-up (#317/#366)	−1.5 to −1.9 pp R@1 @2-bit real data; ≤0.4 pp @4-bit
8	magnitude cliff (#335)	−92.5 pp when hit, all-or-nothing

Combined worst realistic case, same data family so the spread is apples-to-apples (10-nz sparse, n=20k):

config	R@1	R10@10
worst: 2-bit, d=1032, store that saved at 500 docs	0.323	0.505
+ fix calibration only	0.373	0.546 (+4.1)
+ fix dim only	0.883	0.927 (+42.2)
best in family: 4-bit, d=1024, bulk add	0.953	0.971

Total spread 46.6 pp R10@10 / 63.0 pp R@1 — and the dim choice alone is 42 pp of it, roughly 10× the calibration term. So this should be fixed before #317/#366, contrary to the ordering the earlier comments implied.

Methodology control passes: openai-1536 2-bit R@1 0.903 vs published 0.891; GloVe 2-bit 0.5695 vs 0.5637; GloVe 4-bit 0.8553 vs 0.8498.

Fix priority, restated: extra WHT rounds (or internal padding) when the largest power-of-two divisor B ≤ 16 — the gated-K form already prototyped. Failing that, a constructor warning: silently losing half your recall to a dim choice is the worst failure mode on the list.

[RyanCodrai]

⚠️ READ THE COMMENTS, NOT THE BODY. The issue body above says "dense embeddings unaffected" and "this bites sparse / bag-of-words" — that scoping is wrong and was superseded twice. The correct rule is per-coordinate energy concentration, not sparse-vs-dense: dense anisotropic data loses 13–17 pp at 2-bit at the same dims. Real OpenAI embeddings do remain unaffected (that part held throughout). Anyone reading only the body will mis-scope the fix.

[RyanCodrai]

Set aside for a maintainer decision: resolving this changes encoded bytes and/or published accuracy claims, so it is a trade-off call rather than a bug fix. Flagged during an automated issue-fixing pass on 2026-07-30.

[RyanCodrai]

/summary