* 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>
Graph rerank recomputes connected components over mutual
semantic_neighbor edges among the candidates on every query, reading
each candidate's edges from the KG. The resident topology snapshot
already holds corpus-wide clusters built from those edges.
Add search.topology.graph_community_source (reciprocal_edges |
topology_snapshot). topology_snapshot scores candidates that share a
snapshot cluster with the same normalization and falls back to the edge
walk when no snapshot is loaded; graph_community_source in debug stats
reports which ran. The default stays reciprocal_edges until a benchmark
gate shows the snapshot source is at least as good. The retrieval bench
can set it for ablations.
sgcHops, sgcNormalize, bqCandidateLimit and bqPrefixDimension existed
only as struct fields, so no production path could enable them. Resolve
topology.sgc_hops / topology.sgc_normalize into the TopologyManager
build config (hops capped at 4 to bound over-smoothing) and
search.topology.bq_candidate_limit / bq_prefix_dim into the routing
options, request, and fingerprint. The snapshot cache rebuilds only the
route index when the BQ prefix changes. All default to off.
Drop the snapshot interner, which was allocated but never used.
- Add StringInterner in include/yams/search/string_interner.h for
reusable, thread-compatible flyweight string deduplication with
heterogeneous string_view lookups.
- Update TopologyRoutingSnapshot in include/yams/search/topology_routing_session.h
to store zero-copy string_view keys for clustersById and membershipsByDocumentHash,
pointing directly into immutable TopologyArtifactBatch strings.
- Add shared_ptr<StringInterner> to TopologyRoutingSnapshot to intern repeated
lookup and dynamically generated strings.
- Eliminate ~75,000 duplicate heap-allocated std::string objects per cached
snapshot, reducing cache footprint by ~70%.
- Add Catch2 tests in tests/unit/search/string_interner_catch2_test.cpp covering
interning, deduplication, lifetime guarantees, and zero-copy pointer preservation
across snapshot upgrades.
Signed-off-by: trvon <me@trevon.dev>
