Dragan Spiridonov 0d80eb56ec feat(perf): RaBitQ 1-bit signature utility + benchmark (#510 item 8) ...

Ports ruflo's perf-M4 (sign-random-projection + Hamming popcount). Adds
src/shared/utils/rabitq.ts: signSignature (384-bit packed into 12 Uint32
words, 48 bytes), hammingDistance (SWAR popcount), hammingSimilarity, and
topKBySignature (Hamming prefilter gated at N>=100 + exact-cosine rerank of a
recall-aware pool, so output equals exact topK when the true top-k fall in the
pool). 16 tests + scripts/benchmark-rabitq.ts (npm run benchmark:rabitq).

HONEST FINDING (verified, does NOT match ruflo's optimistic 2.7x/10.9x):
  N=1000: speedup 1.31x, recall@10 100%, index 1.46MB -> 47KB (32x smaller)
  N=5000: speedup 1.18x, recall@10 99.9%, 7.32MB -> 234KB (32x smaller)
The 32x INDEX-MEMORY reduction is real and unconditional. The SPEEDUP is only
~1.2-1.5x in JS, not ruflo's figure: a 1-bit sign signature in 384-dim is
coarse, so preserving recall@10 >= 0.95 needs a large exact-rerank pool
(~40-55% of N), which eats most of the prefilter win. ruflo's big win came
from replacing a LINEAR scan; AQE's main search is already native HNSW
(sublinear), so that win doesn't transfer. Tests pin this tradeoff (recall==1.0
with a sufficient pool; small pool sacrifices recall) so it can't be
mis-sold later.

NOT INTEGRATED — no zero-regression consumer exists:
  - unified-memory-hnsw search() IS the ranking (no separate exact rerank to
    prefilter), so Hamming-prefiltering its beam would drop true neighbors;
  - coherence-gate-energy O(N^2) SUM and k-means clustering are numerically
    sensitive (Hamming would change results).
Committed as a tested, benchmarked, ready-to-use utility (real memory lever for
patterns.rvf and a future prefilter->exact-rerank consumer), not wired into any
production path. No production code or .agentic-qe stores touched.

Co-Authored-By: Claude Opus 4.8 (1M context) <noreply@anthropic.com>

2026-06-02 10:30:10 +00:00

8.9 KiB

Raw Permalink Blame History

View Raw