* Add TQ+ ErrorCorrection on top of renorm
Per-coordinate shift+scale fits each rotated, length-rescaled coord onto
the codebook's N(0, 1) grid before quantization. EncodedVectorsTQ::encode
runs a first pass to fit the stats when TQMode::Plus.
Scoring stays correct under renorm's `scaling_factor` framework:
- Asymmetric: precompute_query scales `Q .* D'` and stashes `qm = ⟨Q, M⟩`
on EncodedQueryTQ; score_precomputed adds qm to raw_dot before applying
scaling_factor.
- Symmetric: scalar slow path computes `Σ X+_a X+_b D'_i² + xm_a + xm_b
− ⟨M, M⟩` (xm stored per vector in extras, mm_const cached on
ErrorCorrection). Result feeds the existing `* v1_scale * v2_scale` arms.
SIMD reuse for this path is a follow-up.
Storage layout: TQMode::Plus extras are 4 bytes longer (xm appended after
scaling_factor). Zero-vector inputs skip EC application so renorm's
existing zero-norm guard keeps producing score ≈ 0 within tolerance.
VectorStats refactor: streaming `VectorStatsBuilder` so the Plus first
pass can feed Welford with a reused buffer; `build` now takes `dim`
directly and is generic over `T: Into<f64>`.
Integration tests run on both Normal and Plus via rstest cases.
Co-Authored-By: Claude Opus 4.7 (1M context) <noreply@anthropic.com>
* Fix TQ+ recall regression on non-uniform per-coord variance data
Two compounding bugs in the renorm + TQ+ composition:
1. centroid_norm was measured on `X+` centroids, which have chi-squared
norm distribution across vectors (~10% spread for d=256). renorm
assumed `cn` should be deterministic `sqrt(d)` (just quantization
drift), so the per-vector correction ended up amplifying intrinsic
chi-squared noise into ranking error. Fix: revert EC per coord before
measuring (`c · D' + M`), matching llama-turbo-quant. The reverted
centroids approximate `rescaled` which has length `sqrt(d)` exactly
by construction. dequantize follows the same convention so the
stored `scaling_factor = l2/cn` round-trips back to the original l2.
2. Asymmetric query path pre-scaled `Q* = R_q · D'` before SIMD encoding.
The SIMD encoder normalizes by `max(|input|)`, so a query whose coords
span 5× magnitude (which `R_q · D'` does on real data) loses precision
on the small-D' coords. Fix: keep `rotated` unscaled, store it as a
side field on `EncodedQueryTQ`, and use a scalar decode-and-dot path
for TQ+ (`Σ R_q_i · c_i · D'_i + qm`). SIMD support for this is a
follow-up.
Catches both via `recall_skewed_data` test on data with 8 spike-variance
input coords. Without the fixes, Bits4 Plus dropped to 0.93 vs Normal
0.98; after the fixes, Plus tracks Normal within 2%.
Co-Authored-By: Claude Opus 4.7 (1M context) <noreply@anthropic.com>
* TQ+ asymmetric: skip the SIMD encoding entirely
The TQ+ asymmetric path doesn't use the SIMD-encoded query — it goes
through `score_precomputed_ec` with `rotated_query`. So building the
SIMD form was wasted work + memory. Make `data` an `Option` and only
populate it for the cases that actually use it (Normal mode any distance,
TQ+ L1 via dequantize fallback).
Co-Authored-By: Claude Opus 4.7 (1M context) <noreply@anthropic.com>
* Revert TQ+ to SIMD scoring path
The whole point of TQ+ is that scoring code-paths stay identical between
Normal and Plus modes — only the query precomputation changes. We
pre-scale `Q* = R_q · D'` so the existing SIMD raw_dot computes
`⟨Q · D', X+⟩` directly, then add `qm` and apply renorm's scaling_factor.
Drops `score_precomputed_ec` and `EncodedQueryTQ::rotated_query`. The
recall regression that motivated the scalar fallback was entirely from
the `compute_centroid_norm` bug (measuring `‖X+‖` instead of `‖rescaled‖`)
fixed in the prior commit; SIMD precision was a red herring.
`recall_skewed_data` confirms: Bits4 Normal=0.984 / Plus=0.978, Bits2
Normal=0.902 / Plus=0.908.
Co-Authored-By: Claude Opus 4.7 (1M context) <noreply@anthropic.com>
* TQ+ Bits1: widen query encoding to 12 bits
For 1-bit storage with TQ+, the per-coord `D' = 1/scale` pre-scaling on
the query can push some coords toward the small end of the SIMD encoder's
integer range (which normalizes by `max(|input|)`). At 8 bits those small
coords lose precision; at 12 bits the rounding error drops ~10× per the
existing `test_query_dotprod_matches_reference` parity test.
`Query1bitSimd` is already generic over BITS so this is just a new
`EncodedQueryTQData::Bits1Wide(Query1bitSimd<12>)` variant + a TQ+/Bits1
dispatch in `precompute_query`. Bits2/Bits4 don't need this — their
storage is fine-grained enough that query precision isn't the bottleneck,
and their SIMD encoders aren't generic over BITS today.
Co-Authored-By: Claude Opus 4.7 (1M context) <noreply@anthropic.com>
* are you happy fmt
* TQ+ Bits1Wide: bump to 16-bit query quantization (kernel max)
12 bits helped on real datasets but not enough — push to the kernel's
ceiling of 16. `Query1bitSimd<BITS>` asserts `BITS ∈ [2, 16]`, so this
is the most precision the existing SIMD path can give us before needing
a wider integer kernel.
Co-Authored-By: Claude Opus 4.7 (1M context) <noreply@anthropic.com>
* TQ+: shift by per-coord median, not mean
For 1-bit storage the codebook boundary sits at 0, so post-shift values
are quantized purely by sign. Median is the sign-balance point of the
distribution; mean isn't (skewed coords pull mean off the median).
On anisotropic embeddings — dbpedia-openai being the reference case —
mean-based shift produced a ~60/40 biased sign distribution per coord,
losing 1-bit's representational capacity. Median-based shift restores
50/50 and matches llama-turbo-quant's behavior. Higher bit-widths are
less sensitive but still benefit; the codebook boundaries still lie at
distribution-percentile-aware positions when the data is centered on
the median.
Median requires per-coord samples in memory, so cap the stats pass at
10K vectors. Estimates converge fast (~√N) — 10K is plenty even for
million-vector indexes. The encoding pass still processes every vector.
Co-Authored-By: Claude Opus 4.7 (1M context) <noreply@anthropic.com>
* TQ+ Bits1Wide: revert to 12-bit query quantization
The recall regression on anisotropic data was the mean-vs-median shift,
not query precision. 12 bits is enough headroom for the per-coord D'
pre-scaling and avoids the extra storage of the 16-bit form.
Co-Authored-By: Claude Opus 4.7 (1M context) <noreply@anthropic.com>
* TQ+ Bits1Wide: bump back to 16-bit query quantization
12 bits helped a bit but not enough on the real dataset. Bump to the
kernel's ceiling. If 16 still isn't enough, the next step is checking
whether the gap is real (re-measure llama branch) before widening the
SIMD integer kernel itself.
Co-Authored-By: Claude Opus 4.7 (1M context) <noreply@anthropic.com>
* are you happy clippy
* use mean
* 1bit error correction
* review remarks
* are you happy clippy
* review remarks
---------
Co-authored-by: Claude Opus 4.7 (1M context) <noreply@anthropic.com>
* # This is a combination of 7 commits.
* SameAsStorage default value
* fix coderabbit warnings
* neon for u8 bq
* sse for u8 bq
* fix windows build
* rename function
* add comments
* fmt
* fix arm build
* review remarks
* bq encodings
* are you happy clippy
* are you happy clippy
* are you happy clippy
* are you happy clippy
* gpu tests
* update models
* are you happy fmt
* move additional bits to the end
* fix tests
* Welford's Algorithm
* review remarks
* are you happy clippy
* remove debug println in test
* coderabit nitpicks
* remove unnecessary clone and partialeq
* Use f64 for Welford's Algorithm
* try fix ci
* revert cargo-nextest
* add debug assertions
* Bump Rust edition to 2024
* gen is a reserved keyword now
* Remove ref mut on references
* Mark extern C as unsafe
* Wrap unsafe function bodies in unsafe block
* Geo hash implements Copy, don't reference but pass by value instead
* Replace secluded self import with parent
* Update execute_cluster_read_operation with new match semantics
* Fix lifetime issue
* Replace map_or with is_none_or
* set_var is unsafe now
* Reformat
* bump and migrate to rand 0.9.0
also bump rand_distr to 0.5.0 to match it
* Migrate AVX2 and SSE implementations
* Remove unused thread_rng placeholders
* More random migrations
* Migrate GPU tests
* bump seed
---------
Co-authored-by: timvisee <tim@visee.me>
Co-authored-by: Arnaud Gourlay <arnaud.gourlay@gmail.com>
