1-bit binary quantization (WITH (bit_width = 1)) — design + status

Status: SHIPPED in v2.6.0 — bit_width = 1 builds, scans, inserts and vacuums. The foundation (reloption + rerank default + pure-Rust sign-BQ core) landed earlier; v2.6.0 wired the encode path, the Hamming scan kernel, aminsert, VACUUM and turbovec_check. IVF + 1-bit (WITH (lists = N, bit_width = 1)) is composed after v2.6.0 — see §7.

Two corrections to what this doc originally specified, both recorded below in place:

  • No wire-version bump. §4 said “bump VERSION 7 → 8”. That was written when v7 was current; by the time the encode path landed the format was already at v8, and the right discriminator turned out to be a new kind byte (KIND_BQ = 3), not a version bump. Existing indexes keep kind = SINGLE/COLBERT/GRAPH and decode byte-identically — no REINDEX. The bq_mean_* fields sit at page offset 316, which was reserved-and-zero on every prior version.
  • IVF + 1-bit composes (§7). It was rejected in v2.6.0 (the cell-contiguous layout and per-cell Hamming scan were unwired); it is now implemented, still at wire version 8 with kind = KIND_BQ plus the existing v4 IVF chain fields. No wire bump was needed.

Prior offline study: .agent/notes/BQ_HNSW_FEASIBILITY.md (measured recall + storage; findings respected here, not re-derived).

1. Is 1-bit TurboQuant-at-1-bit, or sign-BQ? — sign-BQ. (kernel evidence)

Decisive: the pinned turbovec crate (rev befc4cbf73ef40e440232ae597888c71fe1ba50c) hard-rejects bit_width < 2 in BOTH constructors:

  • TurboQuantIndex::new(dim, bit_width) — turbovec/src/lib.rs:250: if !(2..=4).contains(&bit_width) { return Err(ConstructError::BitWidthOutOfRange(bit_width)) }.
  • TurboQuantIndex::new_lazy(bit_width) — lib.rs:286: same check.

IdMapIndex::new (the wrapper every pg_turbovec build/scan path calls) delegates to these, so turbovec cannot build a 1-bit index at all. 1-bit is therefore a distinct scheme: sign binary quantization (sign-BQ) — the DiskANN/pgvector/Qdrant coarse code:

TurboQuant (2/¾-bit) sign-BQ (1-bit, this feature)
code rotated + Lloyd-Max codes per-coord sign bit (after centering)
distance rotated dot via LUT Hamming (popcount(XOR)) coarse, then exact heap rerank
per-vec storage dim/8 * bit_width + 4 B scale dim/8, no scale
rotation / codebook yes no
metric cosine / IP angular ≈ cosine (matches the AM’s opclasses)

Even a hypothetical TurboQuant-at-1-bit would degenerate to the sign bit but keep the f32 LUT scorer + 4 B scale — giving up BQ’s whole point (integer popcount speed, half the storage). The scheme that wins storage/latency is sign-BQ + Hamming, exactly what the feasibility study measured.

2. What landed (this branch)

  1. Reloption WITH (bit_width = 1) (src/index/options.rs): the bit_width range is now 1..=4 (was 2..=4). bit_width = 1 with graph = true is rejected (the sign-BQ scan kernel is flat/IVF, not Vamana, yet). The GUC default stays 2..=4 — BQ is opt-in per the study (“never a default”; unusable on non-zero-centered data).

  2. Rerank default auto-widens for 1-bit — but only below 256-d. (src/guc.rs::hi_dim_rerank_candidate_count): gained a bit_width param, so a 1-bit index computes effective_dim = max(dim, 256) instead of dim.

    Read the consequence carefully, because an earlier version of this doc overstated it. The auto window is clamp(effective_dim, 256..=1024). For a 1-bit index that is clamp(max(dim,256), 256..=1024); for 2/¾-bit it is clamp(dim, 256..=1024). Those are the same value for every dim >= 256 — so the 1-bit special case is a no-op at 256-d and above, and only widens the window for dim < 256:

    dim 1-bit auto window 2-bit auto window special case does
    64 256 32 widens 8×
    128 256 32 widens 8×
    192 256 32 widens 8×
    256 256 256 nothing
    768 768 768 nothing
    1536 1024 1024 nothing

    So a 1-bit-vs-2-bit comparison at dim >= 256 and default settings compares equal windows, and any recall or latency difference there is the quantizer, not the knob. Below 256-d the windows differ and the comparison must control for it. (Verified against the driver’s mirror of the Rust clamp during the 2026-09-09 dim sweep, which is what caught the overstatement.)

    Reuses the EXISTING xs_recheckorderby / search_k / oversample machinery — no new rerank mechanism. A user override past the floor still wins (user_count.max(floor)).

  3. Pure-Rust sign-BQ core (src/index/onebit.rs, fully unit-tested, no pgrx cluster needed):

    • pack_signs / unpack_signs: MSB-first sign packing, SAME layout as bitvec.rs / Postgres bit (so the SQL Hamming/popcount kernel and the future index scorer share one convention).
    • corpus_mean + center: the footgun fix — mean-centering. The naive sign-at-zero rule sets every bit to 1 on dense-positive data (GIST: R@10 = 0.0). Subtracting the per-dim corpus mean before the sign splits each dimension. On zero-centered text embeddings the mean is ~0 (centering is a near-no-op).
    • is_degenerate: detects the pathological all-same-sign-after- centering case (every code identical, Hamming uniformly 0) so the build can ERROR instead of shipping an all-ones landmine.
    • codes_stride(dim) == dim/8 — exactly half the 2-bit stride dim/8 * 2 (unit-asserted).

  4. Footgun-safe half-state (src/index/build.rs): until the encode path is wired, a bit_width = 1 build raises a clear ERROR (“not yet implemented … see docs/ONEBIT_BQ.md”) at the single ambuild choke point — NOT a panic (turbovec’s IdMapIndex::new would expect()-panic), NOT a silent success. A 1-bit index can never come into existence, so aminsert/scan paths are unreachable for it. #[pg_test] pg_index_am_onebit_errors_clearly_not_panic asserts this.

3. Storage (confirmed)

Per-vector on-disk codes for a flat/IVF index:

bits codes/vec + scale note
1 (sign-BQ) dim/8 none half of 2-bit
2 dim/8 * 2 4 B
4 dim/8 * 4 4 B

1536d: 1-bit = 192 B, 2-bit = 384 B + 4. The codes_stride unit test asserts 2bit == 2 * 1bit. sign-BQ also drops the per-vector scale (4 B), the persisted rotation matrix (dim*dim*4 O(1)), the Lloyd-Max codebook, and the blocked chain — so the on-disk win is slightly more than exactly 2× at the O(1) terms. The mean vector (dim * 4 bytes, O(1)) is the only NEW header.

4. Wire-format impact — YES, a bump is required (flagged)

A 1-bit index needs a wire bump (VERSION 7 -> 8) because a sign-BQ relfile is NOT byte-decodable by the current reader:

  • no scales chain, no codebook, no rotation chain — the reader must know not to expect them (the meta-page chain-offset fields would be ambiguous otherwise).
  • a NEW mean-vector chain (dim f32) the current meta page has no field for.
  • the codes-chain stride is dim/8 (bit_width = 1), which the existing codes_stride(1, dim) math already produces — that part is fine.

So the bump is real and NOT additive-decodable the way v4->v5->v6 were. Consequences the integration must handle: - bump page::VERSION 7 -> 8 and EXPECTED_WIRE_FORMAT_VERSION in lib.rs (the wire_format_version_is_stable test). - existing v7 indexes decode byte-identical (a v8 binary reads v7 as before) — so no REINDEX for existing 2/4-bit indexes; only a 1-bit index is new-build-only. - add is_legacy_v7() if a future bump needs it (the current is_legacy_v6 gate stays as-is). - migration matrix row in docs/UPGRADING.md; a migrations/NNN_*.sql file (empty is fine — additive). - sequencing: this is a MINOR bump. If it ships in the same release as another wire change, co-design the single bump; otherwise it rebases onto whatever VERSION is current.

This branch does NOT bump the wire format (VERSION untouched, patch- safe) precisely because the encode path that WOULD change the wire is not landed. The bump lands with the encode path, not before.

5. What shipped (v2.6.0) — was “remaining work”

Not landed here because it (a) is a real new scan kernel + wire path that can’t be validated end-to-end in the shared-cluster sandbox, and (b) crosses build/scan/relfile/page/cache. The spec:

  1. Encode branch (build.rs, gated bit_width == 1): compute corpus_mean over the (normalised) corpus, center each vector, is_degenerate check (ERROR with a bit_width >= 2 hint if it trips), pack_signs into the codes chain. Bypass IdMapIndex::new entirely — no scales/rotation/codebook/blocked. This is the parallel analog of the existing flat/IVF encode, minus the turbovec call.
  2. Meta-page v8 (page.rs): a bq: bool (or reuse kind), a mean-vector chain (first/count/bytes), scales/rotation/codebook counts = 0. relfile.rs write/read for the BQ shape.
  3. Scan kernel (cache.rs): a ScanHandle::Bq(Arc<BqIndex>) variant holding packed codes + slot_to_id + the mean. search(query, k) = center the query by the persisted mean, pack_signs, then top-k by Hamming (popcount(q XOR code[i]), ascending). Start SCALAR (bitvec.rs::hamming_distance is the correct reference); SIMD popcount is a follow-up (the v1.7.3-class scalar-fallback correctness lesson applies — test scalar first). [Resolved: §7 — the follow-up landed as a CPU-independent wide-word kernel; AVX2 was measured and declined.] The AM’s xs_recheckorderby already reranks the top-k exactly against the heap — compose, don’t reinvent.
  4. #[pg_test] (the study’s ask): build a bit_width = 1 index over zero-centered synthetic data, assert R@10 >= 0.9 WITH the rerank on a favorable set, assert storage is ~half the bit_width = 2 index over the same data (via pg_relation_size), and assert the all-positive footgun case works-via-centering-or-errors-clearly (never silent garbage). The pure-Rust onebit tests already cover center/pack/ degenerate correctness; the pg_test covers end-to-end recall+storage.
  5. Wire bump + migration + UPGRADING.md row (§4).

IVF WITH (lists = N, bit_width = 1) composes (cell-contiguous sign codes + Hamming per-cell) — implemented after v2.6.0, see §7; the graph kind is explicitly excluded (rejected in options.rs).

6. As-built notes (v2.6.0)

What differed from the spec above, and the bugs found wiring it:

  1. KIND_BQ = 3, not a version bump (see the Status note). A BQ relfile has: a codes chain of dim/8 packed sign bits per vector, an ids chain, and a corpus-mean chain (dim f32). No scales, no codebook, no rotation/TQ+, no blocked chain. MetaPageData::plan_bq is a separate constructor rather than a flag on plan_with_blocked, so a bug in the BQ layout cannot change the layout of any existing index.

  2. Three instances of the v1.24.0 corruption class, found and fixed. write_tombstones_and_meta, the tombstone placement inside the rewrite path, and MetaPageData::total_blocks() each summed chain page counts without bq_mean_count. On a BQ index that would have placed the tombstone chain on top of the mean vector and under-sized the relation — the identical shape of the v1.24.0 graph bug (which omitted graph_count). Found by auditing every chain-offset sum in the tree, not just the path being added.

  3. Degeneracy must be checked on the CENTERED corpus. The first implementation checked the raw corpus, which rejects exactly the dense-positive corpora this feature exists to handle (they are degenerate raw — every sign bit is 1 — and index fine after centering). The existing unit test all_positive_is_degenerate_raw_but_centering_fixes_it says so in its name. CI caught it. The guard still fires for a corpus collapsed after centering (constant / near-constant), where Hamming is uniformly 0 and results would be arbitrary.

  4. The mean is NOT recomputed on aminsert. Recomputing it would invalidate every sign code already packed against the old mean, so a single insert would silently degrade the whole index’s ranking. The build-time mean is treated as fixed; drift is a REINDEX concern, which matches the build-then-serve model the reloption’s guidance already sets out.

  5. VACUUM is tombstone-only, sharing the graph kind’s path (graph_tombstone_dead was already kind-agnostic slot arithmetic). Compacting would require rewriting the whole packed codes chain and renumbering every slot.

  6. turbovec_check skips the scales validation for BQ only. BQ has no scales chain, so the v2.2.2 check that closed the scan-fatal blind spot would otherwise report every BQ index corrupt. It reports kind = 'bq'.

  7. The Hamming kernel is wide-word, and deliberately NOT SIMD. hamming folds 8 bytes at a time through u64::count_ones (one POPCNT per 8 bytes instead of per byte) with a byte-wise tail. That tail loop IS the original scalar kernel and is the only path below dim = 64, so it stays live and covered. There is no is_x86_feature_detected!, no target_feature, no unsafe, and no runtime dispatch anywhere in the module: every machine executes the same instruction sequence over the same word decomposition, so this cannot become a second v1.7.3 (where a mis-specialised kernel returned wrong ANN results on pre-AVX2 CPUs). An AVX2 variant WAS written, proven bit-identical and benchmarked; it was declined — the numbers are in §7 below. Ties break toward the lower slot, and since Hamming over dim bits has only dim + 1 distinct values, ties are the common case — which is why the AM’s exact rerank does the fine ranking and hi_dim_rerank treats a 1-bit index as high-dim at any dim (which only changes the window below 256-d — see item 2).

Still open

  • Graph + 1-bit — rejected in options.rs (and the graph kind is deprecated as of v2.5.0, so this will not be pursued).
  • Recall at scale. DONE 2026-09-08. Measured on arnold (AVX2) over 250k x 1024-d Cohere-wiki with 100 held-out queries and exact ground truth: 3.98x smaller than 4-bit, 2.02x smaller than 2-bit, but 2.7-6.1x the latency at matched recall (ratios CONFIRMED by a clean re-run on 2026-09-10 after the host’s load problem was fixed: 2.75x / 6.09x, with recall reproducing exactly and the original absolute ms ~15% pessimistic – see BQ_RECALL_BENCH.md 0) and a 25x wider rerank window needed to clear R@10 >= 0.99. All four pre-registered predictions held. See docs/BQ_RECALL_BENCH.md § 0 and benches/results/bq_frontier_20260908/.
  • IVF + 1-bit at 1M. MEASURED 2026-09-10 (BQ_RECALL_BENCH.md § 0.6e, benches/results/bq_1m_20260910/). On a real 1M x 1024-d Cohere corpus the crossover EXISTS but is narrow: IVF beats flat by 47% at R@10 >= 0.90 and 38% at >= 0.95, loses by 12% at >= 0.98, and cannot reach

    = 0.99 at all (per-probe ceiling 0.986). For bit_width >= 2 flat wins at every target. IVF storage overhead halves at 1M (+3.1% vs +6.0% at 250k). Two-axis rule: 1-bit + n >= ~1M + target <= ~0.95 -> lists = N; else flat.

  • IVF + 1-bit. MEASURED 2026-09-09 (docs/BQ_RECALL_BENCH.md § 0.6a, benches/results/bq_ivf_20260909/). It builds and scans; storage overhead over flat BQ is +6.0 % (a fixed ~8.5 B/vector of IVF metadata, proportionally worst for the smallest codes). At 250k, flat BQ dominates it: IVF imposes a per-probe-count recall CEILING a wider rerank window cannot break (probes=8 saturates at R@10 0.846 from window 256 through 2000), whereas flat reaches 0.994. That is a scale-dependent result — 250k is below where IVF’s scan-cost advantage pays — so it is a documented boundary, not a verdict.
  • Dimension sweep. DONE 2026-09-09 (docs/BQ_RECALL_BENCH.md § 0.6c, benches/results/bq_dimsweep_20260909/). 1-bit’s penalty shrinks monotonically with dim: the window it needs versus 2-bit for R@10 ≥ 0.95 goes 125× (256-d) → 25× (512-d) → 8× (1024-d), and storage improves too (1.90× → 1.97× vs 2-bit, since fixed per-index overhead amortises away). 1-bit is a high-dimension technique — at 256-d it needs to rerank 6.4 % of the corpus for R@10 ≥ 0.99 and is effectively unusable. The 1024-d arm reproduced the published § 0 recall bit-identically at all 7 windows, which validates both. Caveat: low dims are prefix slices, not native embeddings, so the trend is an upper bound on dim-sensitivity.
  • Real 1M+ scale — still open. A synthetic 1M attempt produced unusable recall because the generated corpus was statistically unrankable (nn1→nn100 spread 6.6–10.4 % vs 37–268 % on a real corpus); discarded with a post-mortem in benches/results/bq_scale_20260909/DISCARDED.md. Needs a REAL 1M corpus. The open question is whether the rerank window needed for a given recall grows with n.
  • Cell-aware incremental INSERT for IVF+BQ — aminsert appends and degrades to a flat Hamming scan (§7 note 4). A real cell-aware insert needs slot insertion + cell-directory renumbering + tombstone-index remapping.
  • Out-of-core IVF+BQ — the BQ scan is RAM-resident (cache::BqIndex holds the whole codes chain). The TurboQuant IVF path has an OOC variant (OocIvfIndex, per-cell gather off the buffer manager); BQ does not. This matters less than for TurboQuant — 1-bit codes are dim/8 bytes, so the resident set is 2-4× smaller than the equivalent 2/4-bit index — but it is the reason a >RAM corpus should still use bit_width >= 2.

7. IVF + 1-bit (WITH (lists = N, bit_width = 1)) — as built

Composed after v2.6.0. Wire version stays 8; the shape is kind = KIND_BQ plus the existing v4 IVF chain fields, so no bump was needed and no existing index is affected.

On-disk shape. Codes (dim/8 per slot, CELL-CONTIGUOUS) → ids (cell order, with soft-assign duplicates) → corpus mean (dim f32) → coarse centroids (lists * dim f32) → cell directory (lists * 12 bytes) → tombstone bitmap (after a VACUUM). Six chains — more than any other kind carries — which is why the chain-offset work below was the riskiest part.

  1. Chain offsets: bq_mean_count added to two more running sums. MetaPageData::set_ivf_chains and set_graph_chain each summed the preceding chains' page counts WITHOUT bq_mean_count. For set_ivf_chains that is live corruption on an IVF+BQ index: the coarse-centroid chain would be placed ON TOP of the corpus mean, so the centring vector every sign code and every query depends on would be overwritten by centroid bytes. For set_graph_chain it is a regression guard only (graph + 1-bit is rejected in options.rs, so no index has both chains). This is the FOURTH occurrence of this class: v1.24.0 omitted graph_count, v2.6.0 found three sites omitting bq_mean_count, and these two were the remaining ones. plan_bq_with_ivf_chains_never_overlap asserts pairwise no-overlap over every present chain and was verified to FAIL when the omission is reintroduced.

  2. No rotation, deliberately. A TurboQuant IVF index trains its coarse cells in the ROTATED space because that is the space its per-vector fine quantizer encodes in — coarse and fine must agree. A BQ index has no rotated fine space (its code is the sign of the centred raw coordinate), so rotating would cost an O(dim²) materialize_rotation_matrix, a GEMM per build block and a rotate_query per scan, and align to nothing. Cells therefore live in the raw L2-normalised space, and scan::ivf_setup_and_search skips the rotation for a BQ handle (ScanHandle::is_bq()) to match. Getting this asymmetric is the sharpest failure mode: a rotated query against un-rotated centroids probes the wrong cells and collapses recall silently — which is what the per-id self-neighbour assertions in onebit_ivf_builds_scans_and_beats_twobit_storage are there to catch.

  3. The mean is permutation-invariant, and computed for free. It is accumulated during the assign sweep (onebit::accumulate_sums per spill block, finish_mean at the end) over the spill in SPILL order, so it is BIT-IDENTICAL to the flat build’s whole-corpus mean — the cell permutation cannot change it, and neither can maintenance_work_mem (block size). Note the mean must be over ROWS, not slots: soft assignment makes n_slots > n_rows, so a slot-order mean would be duplicate-weighted. streamed_mean_matches_whole_corpus_mean gates the block-size invariance.

  4. aminsert DEGRADES to flat, observably. Placing a row in its cell would mean shifting every later slot and renumbering the whole cell directory (and remapping every tombstone bit, which is slot-indexed). Rather than get that subtly wrong, the insert appends and drops the cell metadata: the index falls back to a flat Hamming scan — slower, never wrong (a full scan can only improve recall), never silently lost. Crucially lists is PRESERVED and ivf_degraded stamped, so turbovec.index_is_degraded() returns true and ambeginscan emits the throttled degradation WARNING naming the index. REINDEX restores the cells. (The TurboQuant IVF insert path degrades too but blanks lists outright, so it is NOT reportable — this path is strictly better on that axis.)

  5. Two bugs found in the EXISTING flat-BQ aminsert, both fixed here because the IVF work runs through the same function:

    • It did not re-persist the tombstone bitmap. plan_bq plans a fresh meta with the tombstone fields zeroed, so every insert after a VACUUM silently RESURRECTED every deleted row. This is the M2 bug the graph kind fixed in v2.1.0 via write_full_with_prepared_graph_and_tombstones; the BQ path shipped without the equivalent.
    • It appended unconditionally, so re-inserting an existing heap TID (an UPDATE of the indexed column that reuses the TID) added a SECOND slot for the same row — unbounded growth under repeated upserts, and a duplicate id, which is the exact shape the flat kind’s bijection guard treats as corruption. It now overwrites the existing slot(s) in place and clears any tombstone bit on them. It also gained the graph path’s row-count drift guard (chains must agree with meta.n_vectors before being extended).

  6. VACUUM needed no change. vacuum.rs already routes meta.is_graph() || meta.is_bq() to the kind-agnostic graph_tombstone_dead (pure slot-index bitmap arithmetic), and tombstone bits are slot-indexed, which is exactly what the cell-contiguous layout is ordered by. write_tombstones_and_meta already counted bq_mean_count (fixed in v2.6.0) and counts coarse_count/cell_dir_count.

  7. turbovec_check gained two BQ validations, both inside the same ShareLock as the meta/ids read (the v1.29.1 monitor-consistency invariant): the corpus mean must be dim f32 (a missing mean is scan-FATAL — the scan ERRORs rather than serve uncentred results), and an IVF+BQ cell directory must PARTITION the slots. Without the second, a torn directory silently mis-probes instead of failing — the same blind-spot class as the 2026-09-05 scales field report.

  8. One Hamming heap, two callers. onebit::topk_hamming_slots takes an arbitrary slot iterator; topk_hamming is that function over 0..n. The flat and cell-restricted scans therefore cannot diverge on the tie-break, and the tie-break is slot-id based rather than arrival-order based — load-bearing because coarse_probe yields cells in distance order, so slots arrive out of ascending order. An out-of-range slot (torn cell directory) is skipped, not panicked on.

Not verified

The #[pg_test]s in this change were written but not run: pgrx binds a fixed port with a shared data dir and sibling agents were using it, and this box’s rustc miscompiles the turbovec crate (llvm.x86.avx512.vpdpbusd.512 intrinsic signature mismatch) so cargo pgrx test cannot build here at all. What WAS run: cargo check --features "pg18 pg_test" (clean), the pure-Rust onebit (19) and page (25) unit tests extracted into standalone crates (all pass), and fail-before verification that the new chain-offset and tie-break tests genuinely fail when the bug they guard is reintroduced. CI is the real gate for the #[pg_test]s.

The recall / storage / latency frontier has since been measured — see docs/BQ_RECALL_BENCH.md § 0 for the results (flat at 1024-d, the IVF+BQ arm, and the 256/512/1024-d dimension sweep), § 0.5 for what they do not license, and § 0.6d for the mandatory pre-flight probe before trusting any synthetic corpus. The driver is benches/scripts/bq/bq_frontier.py; artefacts are under benches/results/.

7. Hamming kernel: what was measured, and why AVX2 was declined

“SIMD popcount” was listed as open under §6 note 7. It was investigated. Outcome: shipped the safe wide-word path (measured 4.4–4.8× at embedding dims), declined the AVX2 intrinsics path (only ~1.8× further, and slower than wide-word below dim = 512).

7.1 What was tried

Four kernels, all producing popcount(a XOR b):

kernel how unsafe CPU-dependent
bytewise (was shipped) u8::count_ones per byte no no
u64 (now shipped) u64::count_ones per 8 bytes + byte tail no no
u64x4 as above, 4 independent accumulators, 32 B/iter no no
avx2 pshufb nibble-LUT + vpsadbw, 32 B/iter yes yes

7.2 Latency — the shipped change vs what it replaced

The exact in-tree topk_hamming against the verbatim pre-change byte-wise kernel. Median of 5–7 reps; agreement asserted on every timed fixture. Host: Intel Core Ultra 7 258V (Lunar Lake, AVX2, no AVX-512), random packed codes, k = the two ends of the BQ rerank window.

n dim stride k old (byte-wise) new (u64) speedup
100k 128 16 B 10 1.15 ms 0.52 ms 2.23×
100k 128 16 B 800 1.53 ms 0.90 ms 1.71×
100k 768 96 B 10 6.13 ms 1.28 ms 4.81×
100k 768 96 B 800 6.57 ms 1.48 ms 4.46×
100k 1536 192 B 10 11.94 ms 2.67 ms 4.48×
100k 1536 192 B 800 12.06 ms 3.21 ms 3.76×
1M 768 96 B 10 59.04 ms 13.66 ms 4.32×
1M 768 96 B 800 61.01 ms 13.88 ms 4.39×
4M 768 96 B 10 237.9 ms 54.0 ms 4.40×
4M 768 96 B 800 249.7 ms 57.4 ms 4.35×

The speedup is stable from 9 MiB (L3-resident) to 366 MiB (firmly DRAM), so the scan is not memory-bandwidth-bound at these sizes: the byte-wise kernel ran at ~1.4 GiB/s, the wide-word one at ~6.2 GiB/s and AVX2 at ~11 GiB/s, all far below this host’s DRAM bandwidth.

The win is smallest at low dim (dim = 128 is 16 B/vector, only two words) and largest once several words fit per row, which is where BQ is actually used — BQ exists for 768/1024/1536-d embeddings.

7.3 Why AVX2 was declined

AVX2 vs the shipped wide-word kernel, same host, n = 200k, k = 10, full topk including the heap, median of 9 reps:

dim stride byte-wise u64 (shipped) AVX2 u64 vs byte AVX2 vs byte AVX2 vs u64
32 4 B 1.17 ms 1.27 ms 1.73 ms 0.92× 0.68× 0.72×
64 8 B 1.44 ms 0.80 ms 1.38 ms 1.81× 1.05× 0.58×
128 16 B 2.75 ms 1.27 ms 1.82 ms 2.16× 1.51× 0.70×
256 32 B 5.08 ms 1.17 ms 1.24 ms 4.33× 4.08× 0.94×
384 48 B 7.51 ms 1.93 ms 2.10 ms 3.90× 3.58× 0.92×
512 64 B 9.93 ms 2.42 ms 1.69 ms 4.10× 5.88× 1.43×
768 96 B 14.99 ms 3.30 ms 1.88 ms 4.54× 7.96× 1.75×
1024 128 B 22.35 ms 4.52 ms 2.50 ms 4.94× 8.95× 1.81×
1536 192 B 31.47 ms 6.79 ms 3.78 ms 4.63× 8.32× 1.80×
3072 384 B 64.74 ms 13.63 ms 6.73 ms 4.75× 9.63× 1.81×

Read the last column: AVX2 is a net LOSS below dim = 512 (the 32-byte main loop never runs at dim <= 256, so short rows pay the dispatch and setup for nothing) and worth at most ~1.8× above it. In log terms the wide-word change captures ~73% of the total available reduction (byte-wise → AVX2) at dim = 768, and 69–80% across dim 512–3072 — for zero unsafe and zero CPU-dependent behaviour.

Against that ~1.8× on long rows, the AVX2 path costs:

  • a second unsafe block on the scan hot path;
  • a dim-dependent dispatch threshold, i.e. a second axis of CPU/shape-dependent divergence in a project that already needs a CI layout matrix axis because turbovec’s two scoring layouts diverged enough to flip near-ties;
  • a path CI cannot exercise both sides of. GitHub runners are AVX2, is_x86_feature_detected! is a runtime check, and -C target-feature=-avx2 would not force the fallback at runtime — the same blind spot documented in docs/CI.md that let the v1.7.3 bug ship.

The shipped kernel has none of those properties: one code path, every CPU, every arch.

Also measured and rejected: u64x4 (four independent accumulators) is slower than the plain single-accumulator u64 loop below dim = 1024 (distance-only, n=100k: 2.02× vs 2.66× over byte-wise at dim = 768; it only pulls ahead at dim = 1536, 3.46× vs 2.89×) — LLVM already extracts the ILP, and the manual unroll mostly adds a tail. A deferred-SAD AVX2 variant (reduce vpsadbw once every 31 iterations instead of every iteration) was also written and proven bit-identical; it matched plain AVX2 within noise, because at these strides the reduction is not the bottleneck.

7.4 The bit-identity proof

The change is a word-size refactor, but “obviously a pure refactor” is exactly what was believed about the kernel that shipped wrong ANN results in v1.7.3. So it is proven, in-tree, as plain #[test]s (no cluster — they run under both CI matrix lanes and under a bare cargo test --lib):

  • hamming_agrees_with_bitwise_reference_across_dims — 5720 random code pairs across 143 dims (every dim in 1..=130, so every dim % 8 and dim % 64 residue and every sub-word length, plus 255, 256, 257, 383, 384, 511, 512, 768, 960, 1000, 1024, 1536, 3072) against a bit-by-bit MSB-first reference that shares no code and no word decomposition with the kernel. Also asserts symmetry and zero self-distance on every fixture, and cross-checks the old byte-wise kernel against the same reference.
  • hamming_extremes_agree_at_every_word_boundary — all-zero vs all-ones is exactly dim at 15 dims straddling byte and word boundaries (7/8/9, 63/64/65, 71/72, 127/128/129), the case random fixtures never draw.
  • hamming_counts_sign_disagreements_on_real_vectors — ties the kernel to the semantics: pack real f32 vectors, assert the packed-code Hamming equals a direct count of sign disagreements on the f32s.
  • topk_hamming_agrees_with_bitwise_brute_force_including_ties — 825 top-k cases (11 dims × 5 corpus sizes × 3 query kinds × 5 k) asserting the full (distance, slot) sequence, tie order included, equals a brute-force sort scored by the independent reference. Query kinds include the all-zero code, which maximally saturates ties.
  • topk_fixtures_really_are_tie_dense — guards the above against passing vacuously by asserting the fixtures genuinely collide (≤ dim + 1 distinct distances over 333 rows).
  • topk_tie_break_prefers_the_lower_slot — the tie-break contract in isolation, on an all-identical corpus where every slot ties.

Mutation-tested (each mutation applied to a copy of the module and the suite re-run): dropping the byte tail, from_be_bytes on one operand only (endianness divergence), AND for XOR, silently skipping the last word, and count_zeros for count_ones each fail 3–6 tests. Flipping the top-k tie-break direction, or removing the tie clause while reversing the visit order, each fail exactly the three top-k tests. The AVX2 and u64x4 candidates were held to the same bar in the scratch harness and also passed — they were declined on cost/benefit, not because they disagreed.

One substantive finding en route: under the current ascending visit order the d == worst && slot < worst_slot half of the heap condition never fires (0 firings in 4.2M evaluations over tie-saturated corpora) — a tie is already resolved by arriving later. It is kept, and now documented, because it makes the tie-break a property of the comparison rather than of the loop order: topk_tie_break_prefers_the_ lower_slot still passes with the loop reversed, and fails if the clause or the order is broken alone. A future chunked or parallel BQ scan can therefore reorder safely.

7.5 What was NOT verified

  • No #[pg_test] / cargo pgrx test run. Sibling agents held the shared pgrx cluster (one fixed port, one data dir — see AGENTS.md). Verified instead: cargo check --no-default-features --features "pg18 pg_test" clean in-tree, cargo fmt --check clean, and the module extracted verbatim into a dependency-free scratch crate where all 19 onebit tests pass. The kernel is pure and has no Postgres surface, and BqIndex::search is unchanged, so the #[pg_test] risk is the usual full-suite regression check, not kernel correctness.
  • Single host, single microarchitecture. Numbers are from one Lunar Lake laptop CPU (AVX2, no AVX-512). Not re-measured on arnold (the project’s AVX2 latency host), meh (pre-AVX2), or rv (riscv64). The wide-word kernel has no CPU-feature dispatch, so correctness is architecture-independent by construction; the ratios are not, and per AGENTS.md a published latency claim must come from arnold. Cross-checked one way: forcing -C target-feature=-popcnt (so count_ones lowers to SWAR rather than POPCNT, a proxy for the scalar-path hosts) still gives 2.40× / 4.62× / 4.69× at dim 128/768/1536, against 2.69× / 4.51× / 4.22× with POPCNT enabled — the win comes from doing 1/8 as many count operations, not from the POPCNT instruction.
  • No end-to-end query latency. These are kernel microbenchmarks. A real BQ ORDER BY also pays planning, buffer reads and the exact rerank, so the end-to-end improvement will be smaller than 4.4× by whatever fraction of query time the Hamming scan represents. That fraction was not measured.
  • Big-endian. Argued from the algebra (popcount of XOR is invariant under any shared byte permutation) and asserted by the bitwise reference tests, but no big-endian machine was available to run them on.