TQ loses to the FAISS PQ baseline on bimodal and one-hot-like coordinate distributions

[RyanCodrai]

Found by bug-hunt wave 11 (recall-quality lens). Severity: medium — the only regimes found where TQ is worse than the published baseline.

Same harness as the official recall suite, n=20,000, d=256, 300 queries, FAISS IndexPQ(m = d/4 @2bit, d/2 @4bit, nbits=8, METRIC_INNER_PRODUCT) — the exact baseline README §Recall uses.

data	bits	TQ R@1	FAISS R@1
bimodal (N(0,1) ± 3 per coord, normalized)	2	0.364	0.632
bimodal	4	0.772	0.900
one-hot + 0.01 noise	2	0.068	0.308
one-hot + 0.01 noise	4	0.174	0.324

(bimodal R10@10: 0.518 vs 0.721.)

This contradicts the README's "beats FAISS" framing, which is only ever evaluated on dense unimodal embeddings. One-hot data is tie-heavy so R@1 there is partly arbitrary, but the 4.5x gap vs PQ on identical data is not.

Diagnosis: TQ+ calibration maps the 5/95% quantiles onto a unimodal Beta (encode.rs:195-196), which is the wrong summary for a bimodal marginal. A user-applied dense random pre-rotation did not rescue either case (one-hot 2-bit: 0.080 raw → 0.060 pre-rotated), so this is the codebook/calibration, not rotation mixing.

For contrast, clustered data (50 clusters, σ=0.3) is brutal in absolute terms (2-bit R@1 0.080) but TQ beats FAISS there (0.026) — intrinsic difficulty, not a regression.

Also worth a doc note from the same audit: unnormalized input works correctly (norms are stored; MIPS on log-normally-scaled vectors gives 2-bit R@1 0.710, 4-bit 0.915, identical whether queries are normalized), but neither docs/api.md nor the docstrings state that inputs need not be normalized or that the metric is raw inner product rather than cosine (add.__doc__ is None).

And a measured non-issue: the calibration freeze (#284/#285) costs ≤2pp on real data — cross-corpus shift (openai→GloVe) 2-bit R@1 0.520 frozen vs 0.530 fresh; 4-bit frozen slightly ahead. The one case worth documenting is a tiny first add: first-add of 150 vectors gives 2-bit R@1 0.523 vs 0.603 with a 5,000-vector first add (~8pp) — i.e. "make your first add at least a few thousand vectors".

🤖 Generated with Claude Code

[github-actions]

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

---

Triage

Kind: Bug report (quality limitation, medium severity) — a measured recall regression on specific data distributions, plus two smaller documentation requests bundled in.

Relevant files:

• turbovec/src/codebook.rs — the quantizer's codebook is built for a single-peaked Beta((d−1)/2, (d−1)/2) marginal (see the module doc at codebook.rs:1-7); this unimodality assumption is what breaks on bimodal and one-hot-like data.
• turbovec/src/encode.rs:194-196 — TQ+ calibration fits per-coordinate shift/scale from the 5%/95% quantiles (TQPLUS_P_LO/TQPLUS_P_HI), a summary that misrepresents a two-peaked distribution. Lines 198-204 (TQPLUS_MIN_SAMPLES) are also relevant to the "make your first add a few thousand vectors" doc note.
• README.md §Recall (lines ~125-135) — the "beats FAISS" framing is only evaluated on dense unimodal embeddings; the issue asks for that claim to be scoped.
• docs/api.md and turbovec-python/src/lib.rs — neither states that inputs need not be normalized or that the metric is raw inner product (add.__doc__ is None); the issue requests a doc note.

Summary

This issue reports that turbovec's quantizer gives noticeably worse search accuracy than the standard published baseline it is usually compared against when the input data has an unusual shape. The quantizer is tuned with the assumption that each coordinate of the vectors follows a smooth, single-peaked distribution — which is true for typical dense embeddings, but not for data where coordinates cluster around two separate values, or for sparse "one-hot"-style data where most coordinates are near zero. On those inputs, measurements show turbovec recovering the correct nearest neighbor far less often than the baseline (in the worst case, about 7% of the time versus 31%), which contradicts the README's claim of superior accuracy — a claim that was only ever tested on typical embedding data.

The reporter traces the cause to the calibration step, which summarizes each coordinate's distribution by two quantile points and maps it onto a single-peaked model, and confirms the problem is not fixable by pre-rotating the data. The issue also asks for two documentation additions: a note that input vectors don't need to be normalized (the metric is raw inner product, not cosine — this works correctly but is stated nowhere), and advice to make the first batch of added vectors at least a few thousand strong, since calibration fitted on a tiny first batch measurably hurts accuracy. A previously suspected concern — that calibration frozen from the first batch would degrade later data — was measured and found to be negligible.

[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

[tq-bot]

Summary

This issue reports that turbovec's compression gives noticeably worse search accuracy on certain unusual data shapes. The compression is tuned for typical embedding vectors, whose values are spread smoothly around a single peak. When the values instead cluster around two separate points, or when most values are near zero (sparse, "one-hot"-style data), turbovec finds the true nearest neighbor much less often than a standard alternative technique does on the same data — in the worst case about 7% of the time versus 31%. That undercuts the README's accuracy claims, which were only ever measured on typical embedding data. The reporter traced the cause to the calibration step, which describes each coordinate's distribution with a summary that simply cannot represent a two-peaked shape, and confirmed that the usual workaround of randomly rotating the data first doesn't help.

The issue also bundles in two smaller documentation requests: the docs should say that input vectors don't need to be normalized (this works correctly today but is stated nowhere), and users should be advised to make their first batch of added vectors at least a few thousand strong, since calibrating on a tiny first batch measurably hurts accuracy. A previously suspected problem — that calibration locked in from the first batch would degrade results on later, different data — was measured and turned out to be negligible. The issue is currently set aside for a maintainer decision, because fixing the accuracy gap would change the stored data format and/or the published accuracy claims, making it a trade-off call rather than a straightforward fix.