vyre_primitives/graph/
vector_neighbor_graph.rs

1//! Vector-to-neighbor-graph fusion contract.
2//!
3//! This module is the shared boundary between ANN-style vector ranking and
4//! graph traversal primitives. It constructs a deterministic k-nearest-neighbor
5//! CSR graph from vector rows, traverses that graph from the query-nearest seed,
6//! and records whether graph-ranked top-k matches direct vector top-k.
7
8use std::collections::VecDeque;
9
10/// Schema version for vector-to-graph fusion evidence.
11pub const VECTOR_GRAPH_FUSION_SCHEMA_VERSION: u32 = 1;
12/// Comparator identity shared by benchmark and release evidence.
13pub const VECTOR_GRAPH_FUSION_COMPARATOR: &str = "vector-graph-fusion:v1";
14/// Metric family used by this first fusion contract.
15pub const VECTOR_GRAPH_FUSION_METRIC_FAMILY: &str = "l2-squared-top-k";
16/// Release leaderboard artifact this contract links to.
17pub const VECTOR_GRAPH_FUSION_FRONTIER_LEADERBOARD: &str =
18    "release/evidence/benchmarks/frontier-leaderboard.json";
19
20/// One deterministic top-k row.
21#[derive(Clone, Debug, Eq, PartialEq)]
22pub struct VectorGraphTopKEntry {
23    /// Vector row / graph node id.
24    pub node_id: u32,
25    /// Squared L2 distance encoded with [`f32::to_bits`].
26    pub distance_bits: u32,
27}
28
29impl VectorGraphTopKEntry {
30    #[must_use]
31    fn new(node_id: usize, distance: f32) -> Self {
32        Self {
33            node_id: node_id as u32,
34            distance_bits: distance.to_bits(),
35        }
36    }
37
38    /// Decode the squared L2 distance.
39    #[must_use]
40    pub fn distance(&self) -> f32 {
41        f32::from_bits(self.distance_bits)
42    }
43}
44
45/// Evidence bundle for one vector-to-graph fusion proof.
46#[derive(Clone, Debug, Eq, PartialEq)]
47pub struct VectorGraphFusionEvidence {
48    /// Schema version.
49    pub schema_version: u32,
50    /// Comparator identity.
51    pub comparator: String,
52    /// Dataset identity supplied by the caller.
53    pub dataset_id: String,
54    /// Metric family.
55    pub metric_family: String,
56    /// Release floor identity supplied by the caller.
57    pub release_floor: String,
58    /// Failure mode identity supplied by the caller.
59    pub failure_mode: String,
60    /// Frontier leaderboard artifact linkage.
61    pub frontier_leaderboard_artifact: String,
62    /// Number of vector rows / graph nodes.
63    pub node_count: u32,
64    /// Vector dimension.
65    pub dimension: u32,
66    /// Neighbor count per CSR row.
67    pub neighbor_k: u32,
68    /// Query ranking size.
69    pub rank_k: u32,
70    /// CSR row offsets for the generated neighbor graph.
71    pub csr_offsets: Vec<u32>,
72    /// CSR target nodes for the generated neighbor graph.
73    pub csr_targets: Vec<u32>,
74    /// Direct vector top-k by squared L2 distance.
75    pub direct_top_k: Vec<VectorGraphTopKEntry>,
76    /// Top-k after traversing the neighbor graph from the query-nearest seed.
77    pub graph_traversal_top_k: Vec<VectorGraphTopKEntry>,
78    /// Number of graph nodes reached from the query-nearest seed.
79    pub graph_reached_count: u32,
80    /// Whether graph traversal reached every node.
81    pub traversal_parity: bool,
82    /// Whether graph traversal top-k exactly matches direct vector top-k.
83    pub top_k_stable: bool,
84    /// Blocking reasons for release evidence.
85    pub blockers: Vec<String>,
86}
87
88/// Build vector-to-graph fusion evidence for one query.
89///
90/// # Errors
91/// Returns an actionable error when input shape or metadata is invalid. Parity
92/// failures are recorded in [`VectorGraphFusionEvidence::blockers`] instead of
93/// failing construction so release artifacts can expose exact failure modes.
94pub fn try_vector_graph_fusion_evidence(
95    vectors: &[f32],
96    dimension: usize,
97    neighbor_k: usize,
98    query: &[f32],
99    rank_k: usize,
100    dataset_id: impl Into<String>,
101    release_floor: impl Into<String>,
102    failure_mode: impl Into<String>,
103) -> Result<VectorGraphFusionEvidence, String> {
104    let dataset_id = dataset_id.into();
105    let release_floor = release_floor.into();
106    let failure_mode = failure_mode.into();
107    validate_vector_graph_inputs(
108        vectors,
109        dimension,
110        neighbor_k,
111        query,
112        rank_k,
113        &dataset_id,
114        &release_floor,
115        &failure_mode,
116    )?;
117    let node_count = vectors.len() / dimension;
118    let (csr_offsets, csr_targets) = build_knn_csr(vectors, dimension, neighbor_k);
119    let direct_top_k = top_k_for_nodes(vectors, dimension, query, 0..node_count, rank_k);
120    let reached = traverse_from_seed(
121        direct_top_k[0].node_id as usize,
122        node_count,
123        &csr_offsets,
124        &csr_targets,
125    );
126    let graph_nodes = reached
127        .iter()
128        .enumerate()
129        .filter_map(|(node, reached)| reached.then_some(node));
130    let graph_traversal_top_k = top_k_for_nodes(vectors, dimension, query, graph_nodes, rank_k);
131    let graph_reached_count = reached.iter().filter(|seen| **seen).count();
132    let traversal_parity = graph_reached_count == node_count;
133    let top_k_stable = direct_top_k == graph_traversal_top_k;
134    let mut blockers = Vec::new();
135    if !traversal_parity {
136        blockers.push(format!(
137            "graph traversal reached {graph_reached_count}/{node_count} node(s); Fix: increase neighbor_k, add reciprocal edges, or shard the dataset before claiming graph-ranking parity."
138        ));
139    }
140    if !top_k_stable {
141        blockers.push(
142            "graph traversal top-k differs from direct vector top-k; Fix: preserve candidate recall before using graph ranking evidence."
143                .to_string(),
144        );
145    }
146    Ok(VectorGraphFusionEvidence {
147        schema_version: VECTOR_GRAPH_FUSION_SCHEMA_VERSION,
148        comparator: VECTOR_GRAPH_FUSION_COMPARATOR.to_string(),
149        dataset_id,
150        metric_family: VECTOR_GRAPH_FUSION_METRIC_FAMILY.to_string(),
151        release_floor,
152        failure_mode,
153        frontier_leaderboard_artifact: VECTOR_GRAPH_FUSION_FRONTIER_LEADERBOARD.to_string(),
154        node_count: node_count as u32,
155        dimension: dimension as u32,
156        neighbor_k: neighbor_k as u32,
157        rank_k: rank_k as u32,
158        csr_offsets,
159        csr_targets,
160        direct_top_k,
161        graph_traversal_top_k,
162        graph_reached_count: graph_reached_count as u32,
163        traversal_parity,
164        top_k_stable,
165        blockers,
166    })
167}
168
169fn validate_vector_graph_inputs(
170    vectors: &[f32],
171    dimension: usize,
172    neighbor_k: usize,
173    query: &[f32],
174    rank_k: usize,
175    dataset_id: &str,
176    release_floor: &str,
177    failure_mode: &str,
178) -> Result<(), String> {
179    if dimension == 0 {
180        return Err("Fix: vector graph fusion requires dimension > 0.".to_string());
181    }
182    if vectors.is_empty() {
183        return Err("Fix: vector graph fusion requires at least two vector rows.".to_string());
184    }
185    if vectors.len() % dimension != 0 {
186        return Err(format!(
187            "Fix: vector graph fusion received {} scalar value(s), not divisible by dimension={dimension}.",
188            vectors.len()
189        ));
190    }
191    let node_count = vectors.len() / dimension;
192    if node_count < 2 {
193        return Err("Fix: vector graph fusion requires at least two vector rows.".to_string());
194    }
195    if node_count > u32::MAX as usize {
196        return Err(format!(
197            "Fix: vector graph fusion node_count={node_count} exceeds u32 graph ids; shard the dataset."
198        ));
199    }
200    if dimension > u32::MAX as usize {
201        return Err(format!(
202            "Fix: vector graph fusion dimension={dimension} exceeds u32 evidence fields; shard the vectors."
203        ));
204    }
205    if neighbor_k == 0 || neighbor_k >= node_count {
206        return Err(format!(
207            "Fix: vector graph fusion neighbor_k={neighbor_k} must be in 1..node_count for node_count={node_count}."
208        ));
209    }
210    if rank_k == 0 || rank_k > node_count {
211        return Err(format!(
212            "Fix: vector graph fusion rank_k={rank_k} must be in 1..=node_count for node_count={node_count}."
213        ));
214    }
215    if query.len() != dimension {
216        return Err(format!(
217            "Fix: vector graph fusion query has {} value(s), expected dimension={dimension}.",
218            query.len()
219        ));
220    }
221    if vectors
222        .iter()
223        .chain(query.iter())
224        .any(|value| !value.is_finite())
225    {
226        return Err(
227            "Fix: vector graph fusion requires finite vector and query values.".to_string(),
228        );
229    }
230    if dataset_id.trim().is_empty() {
231        return Err("Fix: vector graph fusion dataset_id cannot be blank.".to_string());
232    }
233    if release_floor.trim().is_empty() {
234        return Err("Fix: vector graph fusion release_floor cannot be blank.".to_string());
235    }
236    if failure_mode.trim().is_empty() {
237        return Err("Fix: vector graph fusion failure_mode cannot be blank.".to_string());
238    }
239    Ok(())
240}
241
242fn build_knn_csr(vectors: &[f32], dimension: usize, neighbor_k: usize) -> (Vec<u32>, Vec<u32>) {
243    let node_count = vectors.len() / dimension;
244    let mut offsets = Vec::with_capacity(node_count + 1);
245    let mut targets = Vec::with_capacity(node_count * neighbor_k);
246    offsets.push(0);
247    for src in 0..node_count {
248        let mut candidates = (0..node_count)
249            .filter(|dst| *dst != src)
250            .map(|dst| {
251                (
252                    squared_l2(row(vectors, dimension, src), row(vectors, dimension, dst)),
253                    dst,
254                )
255            })
256            .collect::<Vec<_>>();
257        candidates.sort_by(|left, right| {
258            left.0
259                .total_cmp(&right.0)
260                .then_with(|| left.1.cmp(&right.1))
261        });
262        targets.extend(
263            candidates
264                .into_iter()
265                .take(neighbor_k)
266                .map(|(_, dst)| dst as u32),
267        );
268        offsets.push(targets.len() as u32);
269    }
270    (offsets, targets)
271}
272
273fn top_k_for_nodes<I>(
274    vectors: &[f32],
275    dimension: usize,
276    query: &[f32],
277    nodes: I,
278    rank_k: usize,
279) -> Vec<VectorGraphTopKEntry>
280where
281    I: IntoIterator<Item = usize>,
282{
283    let mut scored = nodes
284        .into_iter()
285        .map(|node| (squared_l2(row(vectors, dimension, node), query), node))
286        .collect::<Vec<_>>();
287    scored.sort_by(|left, right| {
288        left.0
289            .total_cmp(&right.0)
290            .then_with(|| left.1.cmp(&right.1))
291    });
292    scored
293        .into_iter()
294        .take(rank_k)
295        .map(|(distance, node)| VectorGraphTopKEntry::new(node, distance))
296        .collect()
297}
298
299fn traverse_from_seed(
300    seed: usize,
301    node_count: usize,
302    csr_offsets: &[u32],
303    csr_targets: &[u32],
304) -> Vec<bool> {
305    let mut reached = vec![false; node_count];
306    let mut queue = VecDeque::new();
307    reached[seed] = true;
308    queue.push_back(seed);
309    while let Some(node) = queue.pop_front() {
310        let start = csr_offsets[node] as usize;
311        let end = csr_offsets[node + 1] as usize;
312        for target in &csr_targets[start..end] {
313            let target = *target as usize;
314            if !reached[target] {
315                reached[target] = true;
316                queue.push_back(target);
317            }
318        }
319    }
320    reached
321}
322
323fn row(vectors: &[f32], dimension: usize, row: usize) -> &[f32] {
324    let start = row * dimension;
325    &vectors[start..start + dimension]
326}
327
328fn squared_l2(left: &[f32], right: &[f32]) -> f32 {
329    left.iter()
330        .zip(right)
331        .map(|(left, right)| {
332            let delta = *left - *right;
333            delta * delta
334        })
335        .sum()
336}
337
338#[cfg(test)]
339mod tests {
340    use super::*;
341
342    #[test]
343    fn connected_neighbor_graph_preserves_direct_top_k() {
344        let vectors = [0.0, 1.0, 2.0, 3.0, 4.0];
345        let evidence = try_vector_graph_fusion_evidence(
346            &vectors,
347            1,
348            2,
349            &[0.1],
350            3,
351            "ann.line.connected",
352            "release-floor:ann-vector",
353            "graph-recall-regression",
354        )
355        .expect("Fix: connected vector graph fusion fixture should build.");
356
357        assert!(evidence.blockers.is_empty(), "{evidence:#?}");
358        assert!(evidence.traversal_parity);
359        assert!(evidence.top_k_stable);
360        assert_eq!(evidence.direct_top_k, evidence.graph_traversal_top_k);
361        assert_eq!(evidence.direct_top_k[0].node_id, 0);
362        assert_eq!(evidence.csr_offsets, vec![0, 2, 4, 6, 8, 10]);
363        assert_eq!(
364            evidence.frontier_leaderboard_artifact,
365            VECTOR_GRAPH_FUSION_FRONTIER_LEADERBOARD
366        );
367    }
368
369    #[test]
370    fn disconnected_neighbor_graph_records_recall_blocker() {
371        let vectors = [0.0, 1.0, 100.0, 101.0];
372        let evidence = try_vector_graph_fusion_evidence(
373            &vectors,
374            1,
375            1,
376            &[0.0],
377            2,
378            "ann.line.disconnected",
379            "release-floor:ann-vector",
380            "graph-recall-regression",
381        )
382        .expect("Fix: disconnected vector graph fusion fixture should still build evidence.");
383
384        assert!(!evidence.traversal_parity);
385        assert!(evidence.top_k_stable);
386        assert!(evidence
387            .blockers
388            .iter()
389            .any(|blocker| blocker.contains("graph traversal reached 2/4")));
390    }
391
392    #[test]
393    fn invalid_vector_shape_is_actionable() {
394        let error = try_vector_graph_fusion_evidence(
395            &[0.0, 1.0, 2.0],
396            2,
397            1,
398            &[0.0, 1.0],
399            1,
400            "ann.bad",
401            "release-floor:ann-vector",
402            "shape-regression",
403        )
404        .expect_err("Fix: malformed vector shapes must be rejected.");
405
406        assert!(error.contains("not divisible by dimension=2"));
407    }
408}
vyre_primitives/graph/vector_neighbor_graph.rs

vyre_primitives/graph/
vector_neighbor_graph.rs
