* QuerySimd::dotprod_batch: score a contiguous run of vectors in one call
The entry point for scanning a contiguous run of encoded vectors at a
stride: `out[v]` ← score of the vector at `data[v * stride..]`. It
scores vector by vector for now; the SIMD batch kernels that share the
query loads across vectors follow.
Bench: `query{4,2,1}bit_dotprod_scan` — a hot query against runs of 512
consecutive vectors streaming from DRAM at the TurboQuant stride, per
vector and through `dotprod_batch`.
Co-Authored-By: Claude Fable 5 <noreply@anthropic.com>
* QuerySimd: interleaved AVX-512 batch kernel with a fused reduction
Vectors up to four cache lines are scored in groups of four that share
every query block load and tail mask; the group's independent
accumulators keep `VPDPBUSD` saturated while one vector's reduction
overlaps with the next group's loads. Longer vectors keep the
per-vector walk, since the hardware prefetcher streams four interleaved
byte streams far worse than one (measured at the 4-bit width: +10 % at
dim 512, 2× slower at dim 1024).
The per-vector reduction fuses the query bytes before the horizontal
sum — `low + K · high` in i32 lanes, then one tree that widens to i64
at the end — for vectors within a per-width lane bound derived from the
encoding (2040 bytes at 4 bits, 1020 at 2, 255 for the wide 1-bit
query; unbounded for a one-byte query). A test pins the derivation to
the hand-computed 4-bit value and drives every width to its bound with
the heaviest possible inputs.
Bench: `batch_avx512_vnni` rows in the scan groups.
Co-Authored-By: Claude Fable 5 <noreply@anthropic.com>
* QuerySimd: AVX2 batch kernel; one fused reduction for AVX2 and AVX-512
The AVX2 batch kernel scores vectors one at a time: its loop-carried
chain is a single `vpaddd` per accumulator (the `maddubs → madd`
products hang off the loads), so interleaving vectors only adds
register pressure on the 16 YMM registers — measured 10–15 % slower
with groups of two or four at the 4-bit width.
The AVX2 per-vector reduction now uses the same fused tree as the
AVX-512 one, within the same per-width lane bound; the bound test
drives both kernels.
Bench: `batch_avx2` rows in the scan groups.
Co-Authored-By: Claude Fable 5 <noreply@anthropic.com>
* QuerySimd: copy the tail block in constant-size pieces
The SSE, AVX2 and NEON kernels run their last partial block on a
zero-padded copy of the remaining bytes. A `len`-byte copy compiles to
a `memcpy` call plus a `memset` for the padding — and the call forces
the accumulators out of their registers around it. Copy in power-of-
two pieces of constant size instead: `len` is the same for every vector
of a query, so the piece branches predict perfectly.
Co-Authored-By: Claude Fable 5 <noreply@anthropic.com>
* QuerySimd: interleaved NEON batch kernels
The SDOT and plain NEON block loops take `N` vectors at a stride, and
the batch entry points score vectors up to four cache lines in groups
of four — the same policy as the AVX-512 kernel, with the group
threshold carried over from the AVX-512 measurement rather than tuned
on ARM hardware.
Bench: `batch_neon` and `batch_neon_sdot` rows in the scan groups.
Co-Authored-By: Claude Fable 5 <noreply@anthropic.com>
---------
Co-authored-by: Claude Fable 5 <noreply@anthropic.com>
* TQ SIMD: one backend ladder, resolved once per query
The 2- and 4-bit kernels share the same preference order (AVX-512 VNNI
→ AVX2 → SSE → NEON + SDOT → NEON → scalar), spelled out six times as
chains of `is_x86_feature_detected!` — and `Query{2,4}bitSimd::dotprod`
re-ran its chain for every vector scored.
Move the ladder into one `simd::SimdBackend` enum with a single `detect()`.
The query types resolve it in `new()` and dispatch on the stored value;
the symmetric `score_{2,4}bit_internal*` entry points dispatch on
`SimdBackend::detect()`.
Co-Authored-By: Claude Fable 5 <noreply@anthropic.com>
* QuerySimd: one query layout and scalar reference for every packing width
`Query{1,2,4}bitSimd` are three copies of the same idea — quantize the
query into i8 halves, multiply them against an integer codebook — each
with its own query layout and its own set of SIMD kernels. Introduce
`simd::query::QuerySimd<PLANES>`, generic over the number of codes per
packed byte (2, 4 or 8), which the three widths will share.
The query halves are stored as planes, one per code position within a
byte: plane `k` entry `j` is the half of query dim `PLANES · j + k`.
That is the order the codes come out of raw data bytes with a shift and
a mask, so a kernel never has to unpack them into dim order. Planes are
zero-padded to the widest SIMD block, so a partial last block on the
data side multiplies against zeros.
The widths contribute only their integer encoding (`Encoding`: codebook
table, offset, scale and query range); the 1-bit width gets one here —
`{0, 128}` with offset 64 on x86_64, `∓127` on aarch64 — chosen so the
query keeps full i8 halves. Only the scalar reference exists yet; the
SIMD kernels follow, and the width types switch over once they're in.
Co-Authored-By: Claude Fable 5 <noreply@anthropic.com>
* QuerySimd: AVX-512 VNNI kernel on the query planes
One ZMM of packed codes per block; for each plane the codes are shifted
down by the code width, masked and looked up in the codebook with one
`vpshufb`, then `VPDPBUSD` folds them into the plane's low and high
accumulators. Two accumulator pairs per vector keep the VNNI latency
off the critical path at every width. The last partial block is a
masked load whose dead lanes multiply against the planes' zero padding.
The shift count is an immediate, so the shift-by-width helper spells
out the three widths in a `match` — the only place the kernel is not
literally generic over `PLANES`.
Co-Authored-By: Claude Fable 5 <noreply@anthropic.com>
* QuerySimd: NEON SDOT kernel on the query planes
The AVX-512 kernel's shape on 128-bit registers: one `TBL` codebook
lookup per plane, `SDOT` (inline asm — `vdotq_s32` is still unstable)
into two accumulator pairs. The last partial block runs on a
zero-padded copy of the remaining bytes.
Co-Authored-By: Claude Fable 5 <noreply@anthropic.com>
* QuerySimd: AVX2 kernel on the query planes
One YMM of packed codes per block, one `vpshufb` lookup per plane and
`maddubs → madd` against ones into the same two accumulator pairs as
the VNNI kernel. The `maddubs` pair sums stay inside i16 by the
per-width query bounds.
Co-Authored-By: Claude Fable 5 <noreply@anthropic.com>
* QuerySimd: SSE and plain NEON kernels on the query planes
The 128-bit forms of the AVX2 and SDOT kernels: `maddubs → madd` on
XMM, `vmull_s8 → vpadalq_s16` on NEON without `dotprod`. Every backend
of the shared query type now has its kernel.
Co-Authored-By: Claude Fable 5 <noreply@anthropic.com>
* Query4bitSimd: score through QuerySimd<2>
`Query4bitSimd` becomes an alias of the shared query type; its own
chunk-and-tail query layout and the per-backend kernels built on it go
away, along with the accuracy tests the shared module now runs for
every width. What stays in `query4bit` is the 4-bit encoding and the
symmetric `score_4bit_internal*` paths.
Co-Authored-By: Claude Fable 5 <noreply@anthropic.com>
* Query2bitSimd: score through QuerySimd<4>
The 2-bit asymmetric kernels unpacked every 4 packed bytes into 16
centroid bytes through two `pshufb` / `TBL` pair-table lookups and a
zip before a single multiply-accumulate step — on AVX-512 that was four
128-bit unpacks and six lane inserts per pair of `VPDPBUSD`. On the
query planes the same 16 codes cost one shift, one mask and one lookup
per plane, straight from a full-width load.
`Query2bitSimd` becomes an alias of the shared query type; its chunk
layout and per-backend kernels go away. The pair-table unpack stays
for the symmetric `score_2bit_internal*` paths.
Co-Authored-By: Claude Fable 5 <noreply@anthropic.com>
* Query1bitSimd: score through QuerySimd<8>
The 1-bit asymmetric kernels bit-plane-transposed the query and scored
`Σ_b 2^b · popcount(data AND plane_b)` per 16-byte block — eight
AND + popcount + add steps on XMM (even with AVX-512, through the VL
forms) and a `BITS`-deep accumulator array. On the query planes a
sign bit is just a one-bit code: shift, mask, a two-entry codebook
lookup and the same multiply-accumulate as the wider widths, on full
256-/512-bit registers.
`Query1bitSimd` becomes an alias of the shared query type. Its query
width was a const parameter (8 bits by default, 16 for TQ+ through the
`Bits1Wide` variant); the shared encoding always carries 16-bit halves,
so the variant and the TQ+ special case go away. The popcount kernels
stay for the symmetric `score_1bit_internal`, where XOR + popcount is
the right tool.
Co-Authored-By: Claude Fable 5 <noreply@anthropic.com>
* Bench: cold per-vector rows for every width
`query{4,2,1}bit_dotprod_cold` from one generic body — scalar reference,
public `dotprod` and each backend — so the widths can be compared on one
host. `TURBO_SIMD_DIMS` narrows or widens the dims of a run and
`TURBO_SIMD_POOL_KB` shrinks the pool to L1 for hot-kernel numbers.
Co-Authored-By: Claude Fable 5 <noreply@anthropic.com>
* QuerySimd: query bytes as a parameter; 8-bit queries for the 1-bit width
The shared kernels always carried two query bytes (a ~16-bit query),
which cost the 1-bit width its 8-bit-query speed: the old bit-plane
kernel scored a 16-byte vector in 4.9 ns hot (34.7 ns cold) against
9.1 ns (54.7 ns) through the planes, the difference being the second
byte's multiply-accumulates on a vector that fills a quarter of one
block. Above 512 dims the planes win either way.
Make the number of query bytes a parameter: `QuerySimd<PLANES,
QUERY_BYTES>` with one plane per query byte and code position, and one
accumulator pair per query byte. A one-byte query is scaled to the
range of a single byte, `RADIX / 2 − 1`. `Query1bitSimd` is the
one-byte instance — at parity with the old kernel at small dims (cold
36.9 / 38.3 / 38.4 ns at d = 128 / 256 / 512) and 1.8× faster at 1536
(68 vs 121 ns) — and `Query1bitWideSimd` the two-byte one, which TQ+
selects through the `Bits1Wide` variant as before. The 2- and 4-bit
widths keep two bytes.
Bench: `query1bit_wide_dotprod_cold` and a `query1bit_wide` row next
to BQ.
Co-Authored-By: Claude Fable 5 <noreply@anthropic.com>
---------
Co-authored-by: Claude Fable 5 <noreply@anthropic.com>
`cargo audit` flags rand 0.7.3 as unsound (RUSTSEC-2026-0097), and
permutation_iterator 0.1.2 is its sole importer. The crate is
unmaintained, so the finding is permanent for as long as we depend on
it.
Everything we used it for is "pick k distinct random indices out of n",
which is exactly `rand::seq::index::sample` from the workspace rand.
Switch the three src call sites and the two benches over, and drop the
dependency. 11 crates leave Cargo.lock.
Also fix a comment in quantile.rs claiming the permutation was
deterministic per count: the old crate keyed itself from thread_rng on
every call, so it never was.
Co-authored-by: Claude Opus 5 (1M context) <noreply@anthropic.com>
* Benches: use SmallRng instead of ChaCha12-based generators
All benchmarks used StdRng or rand::rng() (ThreadRng), both backed by the
ChaCha12 block cipher in rand 0.10. Benchmarks do not need crypto-strength
randomness, and several draw random values inside the timed closure, so
cipher work was included in the measurement itself.
Switch every bench target to SmallRng (Xoshiro256++), and key the HNSW
graph cache and sparse index cache by RNG algorithm so stale caches built
from the old generator are not reused against newly generated vectors.
Co-Authored-By: Claude Fable 5 <noreply@anthropic.com>
* Benches: replace free-function rand::random with local SmallRng
Addresses review: rand::random draws from the thread RNG (ChaCha12),
including inside the timed loop of the pq score benchmark.
Co-Authored-By: Claude Fable 5 <noreply@anthropic.com>
---------
Co-authored-by: Claude Fable 5 <noreply@anthropic.com>
* Remove from_iter_instead_of_collect from workspace lints
The lint was removed from clippy (beta) and now triggers
renamed_and_removed_lints warnings in every crate.
Co-Authored-By: Claude Fable 5 <noreply@anthropic.com>
* Fix clippy::chunks_exact_to_as_chunks
Replace chunks_exact with a constant chunk size by as_chunks.
Co-Authored-By: Claude Fable 5 <noreply@anthropic.com>
* Fix clippy::needless_late_init
Co-Authored-By: Claude Fable 5 <noreply@anthropic.com>
* Fix clippy::useless_borrows_in_formatting
Co-Authored-By: Claude Fable 5 <noreply@anthropic.com>
* Fix clippy::uninlined_format_args
Co-Authored-By: Claude Fable 5 <noreply@anthropic.com>
* Fix clippy::for_kv_map
Iterate map values directly instead of discarding keys.
Co-Authored-By: Claude Fable 5 <noreply@anthropic.com>
* Allow clippy::result_large_err on QueueProxyShard::new_from_version
The Err variant intentionally hands the LocalShard back to the caller.
Same pattern as the existing allow on ForwardProxyShard::new.
Co-Authored-By: Claude Fable 5 <noreply@anthropic.com>
* Allow clippy::result_unit_err on wait_for_consensus_commit
Co-Authored-By: Claude Fable 5 <noreply@anthropic.com>
---------
Co-authored-by: Claude Fable 5 <noreply@anthropic.com>
* quantization over tq strorage
are you happy fmt
are you happy clippy
rotation refactor
rotation refactor
fix tests
better test name
review remarks
dont rotate query in raw scorer
tq sources revert
quantized_scoring_datatype revert
simplify
are you happy fmt
* remove old comments
* review remarks
* 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>
