* test(topology): characterize degree representatives and raw BQ sign bits
Pin the current behaviour before adding opt-in representative and BQ
rotation options:
- connected, louvain and kmeans engines on a skewed cluster (dense
clique plus a weak-edge hub): medoid hash, score, extra routing
representatives and roles;
- equal-degree ties go to the smaller document hash;
- the unrotated BinaryQuantizedIndex matches a raw-coordinate sign-bit
reference, with and without a prefix dimension.
Signed-off-by: trvon <me@trevon.dev>
* feat(topology): add an opt-in medoid representative rule
topology.representative_rule = degree (default) | medoid selects how a
cluster's representative document is chosen. Degree keeps the max
within-cluster weighted degree. Medoid picks the member minimising
sum_j sqrt(max(0, 2(1 - cos))) over the other members.
- one shared helper, applyRepresentativeRule(), is called by the
connected, louvain and kmeans engines after their unchanged degree
choice; medoid falls back to it without usable geometry;
- clusters above 256 usable members are searched on a deterministic
hash-ordered stride sample (kMedoidRepresentativeMaxMembers);
- ties within 1e-9 go to the smaller document hash;
- with medoid, farthest-first extra routing representatives are seeded
from the medoid instead of the centroid;
- the rule is stored in the formerly reserved first header byte of the
binary snapshot (0 = degree, so old snapshots keep their meaning) and
extends the construction fingerprint only when it is not degree;
- search debug stats report topology_representative_rule.
Signed-off-by: trvon <me@trevon.dev>
* feat(topology): add an opt-in randomized Hadamard rotation for BQ routing
search.topology.bq_rotation = none (default) | fwht selects the rotation
applied before the centroid BQ shortlist takes sign bits. Raw-coordinate
sign bits make cos(pi * h / d) a poor estimate on anisotropic embeddings;
after x -> (1/sqrt(n)) H D [x; 0] every bit is a random hyperplane.
- RandomizedHadamardRotation in yams/vector: fixed splitmix64 sign
diagonal plus an in-place FWHT, zero-padded to a power of two; Simeon's
FWHT projection works on int32 sketches with row subsampling, so a
small local transform is used instead;
- BinaryQuantizedIndex::build() takes the rotation and seed, rotates
stored vectors before the prefix is taken, and rotates every float
query itself, so centroids and queries always share one seed
(kDefaultBinaryRotationSeed);
- the routing snapshot cache records bqRotation and bqRotationSeed and
rebuilds the route index when either differs;
- the routing policy fingerprint changes only for a non-default rotation;
- search debug stats report topology_route_bq_rotation.
Signed-off-by: trvon <me@trevon.dev>
* test(bench): map representative rule and BQ rotation arm knobs
Harness-only env knobs written into the isolated benchmark config.toml,
so arms go through ConfigResolver like the other topology settings:
- YAMS_BENCH_TOPOLOGY_REPRESENTATIVE_RULE=degree|medoid
-> [topology] representative_rule
- YAMS_BENCH_TOPOLOGY_BQ_ROTATION=none|fwht
-> [search.topology] bq_rotation, next to bq_candidate_limit and
bq_prefix_dim
The debug-file setup entry records the requested values; per-query
search_stats carry the effective topology_representative_rule and
topology_route_bq_rotation. Portability allowlist lines are shifted for
the inserted code.
Signed-off-by: trvon <me@trevon.dev>
---------
Signed-off-by: trvon <me@trevon.dev>
Implement three research-backed retrieval optimizations connecting
paperbridge literature findings with YAMS subsystems:
1. SGC Feature Smoothing (Proposal A):
- Add sgcHops and sgcNormalize to TopologyBuildConfig.
- Diffuse document embeddings across reciprocal nearest-neighbor graph
edges prior to clustering, formalizing Lean SGC.lean.
- Re-normalize diffused embeddings to preserve unit hypersphere metric geometry.
- Wire into ConnectedComponent, Louvain, and KMeans topology engines.
2. Matryoshka Prefix Binary Quantization (Proposal C):
- Add maxDimensions parameter to BinaryQuantizer::quantize and
maxPrefixDimension to BinaryQuantizedIndex::build.
- Support fast 64-bit word-aligned prefix Hamming shortlisting in
SparseGuidedClusterRouter via bqPrefixDimension.
3. Fragment Outer-MaxSim Reranker (Proposal B):
- Implement SimeonScoringMode { SingleVectorCosine, FragmentOuterMaxSim }
in SimeonModelProvider.
- Add extractDocumentFragments and late-interaction outer-MaxSim scoring
inspired by ColBERTv2/PLAID/SPLATE to prevent relevance dilution in long docs.
- Expose simeonRerankOuterMaxSim on SearchEngineConfig and ConfigResolver.
- Add Catch2 test coverage and verify BEIR scifact benchmark metrics.
Signed-off-by: trvon <me@trevon.dev>
- Add BinaryQuantizer and BinaryQuantizedIndex in include/yams/vector/binary_quantization.h
and src/vector/binary_quantization.cpp implementing 1-bit sign quantization,
packed 64-bit word storage, hardware popcount Hamming distance, and cosine
similarity estimation.
- Integrate centroidBqIndex into SparseRouteIndex, constructing compact BQ
centroids alongside dense ANN indices during SparseGuidedClusterRouter::buildRouteIndex.
- Add bqCandidateLimit to TopologyRouteRequest and tracking metrics (bqUsed,
bqCandidates, bqDistanceEvaluations) to SparseRouteWork.
- Enable fast candidate pre-filtering in SparseGuidedClusterRouter::route with
1-bit Hamming distance scans, providing sub-millisecond coarse candidate
shortlisting and automatic fallback when the dense ANN index is omitted.
- Add Catch2 unit test suites in tests/unit/vector/binary_quantization_catch2_test.cpp
and tests/unit/topology/topology_baseline_catch2_test.cpp.
Signed-off-by: trvon <me@trevon.dev>
