Skip to main content

qualia_core_db/services/swarm/
verify.rs

1//! Result verification — the trusted gate that runs *before* payment. It never trusts
2//! the executor; it re-derives correctness cheaply with a local reference.
3//!
4//! * **Dense matrix product** → **Freivalds' algorithm**: to check `A·B = C` without
5//!   recomputing the `O(n³)` product, pick a random ±1 vector `x` and test
6//!   `A(Bx) == Cx` in `O(n²)`. A wrong `C` passes a single round with probability ≤ ½,
7//!   so `r` independent rounds bound the false-accept probability by `2⁻ʳ`. This makes
8//!   verify-before-pay *cheaper than doing the work* — essential for the economics.
9//! * **Embedding artifact** → **ranking reproduction**: a trained table is trusted only
10//!   if it actually ranks the held-out check triples well (MRR ≥ floor) — termination is
11//!   not evidence of learning.
12
13use super::job::{JobInput, JobResult};
14use crate::solvers::linear_algebra::gemm::{matvec, Transpose};
15use crate::solvers::optimization::metaheuristics::Rng;
16
17/// The verdict of verifying a returned result against the job's input.
18#[derive(Debug, Clone, Copy, PartialEq)]
19pub enum VerificationVerdict {
20    /// Result re-derives correctly; `confidence` ∈ (0,1] (1 − false-accept bound).
21    Verified { confidence: f64 },
22    /// Result does not match the trusted reference — do not pay.
23    Rejected { reason: &'static str },
24}
25
26impl VerificationVerdict {
27    /// `true` when verified.
28    pub fn is_verified(&self) -> bool {
29        matches!(self, VerificationVerdict::Verified { .. })
30    }
31}
32
33/// Tunables for verification.
34#[derive(Debug, Clone, Copy)]
35pub struct VerifyPolicy {
36    /// Freivalds rounds (false-accept ≤ 2⁻ʳ). More rounds = more confidence.
37    pub freivalds_rounds: usize,
38    /// Numeric tolerance for the product check (floating-point slack).
39    pub tol: f64,
40    /// RNG seed for the random projection vectors (deterministic, auditable).
41    pub seed: u64,
42    /// Minimum MRR an embedding artifact must achieve on the check set to be accepted.
43    pub min_mrr: f64,
44}
45
46impl Default for VerifyPolicy {
47    fn default() -> Self {
48        Self {
49            freivalds_rounds: 16,
50            tol: 1e-6,
51            seed: 0xF1E1,
52            min_mrr: 0.9,
53        }
54    }
55}
56
57/// Verify a result against the job input. Mismatched kinds are rejected (fail closed).
58pub fn verify(input: &JobInput, result: &JobResult, policy: VerifyPolicy) -> VerificationVerdict {
59    match (input, result) {
60        (JobInput::DenseLinearProduct { m, k, n, a, b }, JobResult::DenseLinearProduct { c }) => {
61            if c.len() != m * n {
62                return VerificationVerdict::Rejected {
63                    reason: "result has wrong dimensions",
64                };
65            }
66            verify_product(*m, *k, *n, a, b, c, policy)
67        }
68        (
69            JobInput::EmbeddingArtifact {
70                n_entities, check, ..
71            },
72            JobResult::EmbeddingArtifact { table },
73        ) => verify_artifact(table, check, *n_entities, policy.min_mrr),
74        _ => VerificationVerdict::Rejected {
75            reason: "result kind does not match job kind",
76        },
77    }
78}
79
80/// Freivalds' check that `C == A·B`. `A` is `m×k`, `B` is `k×n`, `C` is `m×n`.
81fn verify_product(
82    m: usize,
83    k: usize,
84    n: usize,
85    a: &[f64],
86    b: &[f64],
87    c: &[f64],
88    policy: VerifyPolicy,
89) -> VerificationVerdict {
90    let mut rng = Rng(policy.seed ^ 0x5A17_C0DE);
91    let mut x = vec![0.0; n];
92    let mut bx = vec![0.0; k];
93    let mut abx = vec![0.0; m];
94    let mut cx = vec![0.0; m];
95    for _ in 0..policy.freivalds_rounds.max(1) {
96        // Random ±1 projection vector.
97        for xi in x.iter_mut() {
98            *xi = if rng.unit() < 0.5 { -1.0 } else { 1.0 };
99        }
100        // bx = B·x  (B is k×n)
101        if matvec(Transpose::No, k, n, b, &x, &mut bx).is_err() {
102            return VerificationVerdict::Rejected {
103                reason: "reference matvec failed",
104            };
105        }
106        // abx = A·(Bx)  (A is m×k)
107        if matvec(Transpose::No, m, k, a, &bx, &mut abx).is_err() {
108            return VerificationVerdict::Rejected {
109                reason: "reference matvec failed",
110            };
111        }
112        // cx = C·x  (C is m×n)
113        if matvec(Transpose::No, m, n, c, &x, &mut cx).is_err() {
114            return VerificationVerdict::Rejected {
115                reason: "reference matvec failed",
116            };
117        }
118        for i in 0..m {
119            if (abx[i] - cx[i]).abs() > policy.tol {
120                return VerificationVerdict::Rejected {
121                    reason: "A·B ≠ C (Freivalds)",
122                };
123            }
124        }
125    }
126    let confidence = 1.0 - 2.0_f64.powi(-(policy.freivalds_rounds.max(1) as i32));
127    VerificationVerdict::Verified { confidence }
128}
129
130/// Verify a trained embedding table reproduces good ranking on the held-out checks.
131///
132/// Uses a **pessimistic** rank (ties counted *against* the true tail): a degenerate
133/// table that scores every candidate equally — e.g. an all-zero "trained nothing"
134/// table — then ranks the true tail last, scoring near-zero MRR and being rejected.
135/// (Optimistic tie-breaking would let such a table masquerade as perfect.)
136fn verify_artifact(
137    table: &crate::solvers::learning::kg_embedding::EmbeddingTable,
138    check: &[(usize, usize, usize)],
139    n_entities: usize,
140    min_mrr: f64,
141) -> VerificationVerdict {
142    if check.is_empty() {
143        return VerificationVerdict::Rejected {
144            reason: "no check set to verify the artifact",
145        };
146    }
147    let mut recip_sum = 0.0;
148    for &(h, r, t) in check {
149        let target = match table.score(h, r, t) {
150            Ok(s) => s,
151            Err(_) => {
152                return VerificationVerdict::Rejected {
153                    reason: "artifact could not be scored",
154                };
155            }
156        };
157        // Pessimistic rank: 1 + #{ other candidates scoring ≥ the true tail }.
158        let mut rank = 1usize;
159        for c in 0..n_entities {
160            if c == t {
161                continue;
162            }
163            match table.score(h, r, c) {
164                Ok(s) if s >= target => rank += 1,
165                Ok(_) => {}
166                Err(_) => {
167                    return VerificationVerdict::Rejected {
168                        reason: "artifact could not be scored",
169                    };
170                }
171            }
172        }
173        recip_sum += 1.0 / rank as f64;
174    }
175    let mrr = recip_sum / check.len() as f64;
176    if mrr >= min_mrr {
177        VerificationVerdict::Verified { confidence: mrr }
178    } else {
179        VerificationVerdict::Rejected {
180            reason: "artifact MRR below the acceptance floor",
181        }
182    }
183}
184
185#[cfg(test)]
186mod tests {
187    use super::*;
188    use crate::solvers::learning::kg_embedding::{train, ScoreModel, TrainConfig};
189
190    #[test]
191    fn freivalds_accepts_a_correct_product() {
192        // [[1,2],[3,4]]·[[5,6],[7,8]] = [[19,22],[43,50]]
193        let input = JobInput::DenseLinearProduct {
194            m: 2,
195            k: 2,
196            n: 2,
197            a: vec![1.0, 2.0, 3.0, 4.0],
198            b: vec![5.0, 6.0, 7.0, 8.0],
199        };
200        let good = JobResult::DenseLinearProduct {
201            c: vec![19.0, 22.0, 43.0, 50.0],
202        };
203        assert!(verify(&input, &good, VerifyPolicy::default()).is_verified());
204    }
205
206    #[test]
207    fn freivalds_rejects_a_wrong_product() {
208        let input = JobInput::DenseLinearProduct {
209            m: 2,
210            k: 2,
211            n: 2,
212            a: vec![1.0, 2.0, 3.0, 4.0],
213            b: vec![5.0, 6.0, 7.0, 8.0],
214        };
215        // One entry corrupted.
216        let bad = JobResult::DenseLinearProduct {
217            c: vec![19.0, 22.0, 43.0, 999.0],
218        };
219        assert!(!verify(&input, &bad, VerifyPolicy::default()).is_verified());
220    }
221
222    #[test]
223    fn freivalds_rejects_a_subtly_wrong_product() {
224        // A single-element error of 1.0 — must still be caught with high probability.
225        let n = 6;
226        let a: Vec<f64> = (0..n * n).map(|i| (i % 7) as f64).collect();
227        let b: Vec<f64> = (0..n * n).map(|i| (i % 5) as f64 - 2.0).collect();
228        let mut c = vec![0.0; n * n];
229        crate::solvers::linear_algebra::gemm::matmul(n, n, n, &a, &b, &mut c).unwrap();
230        let input = JobInput::DenseLinearProduct {
231            m: n,
232            k: n,
233            n,
234            a,
235            b,
236        };
237        c[10] += 1.0; // corrupt one cell
238        let bad = JobResult::DenseLinearProduct { c };
239        assert!(!verify(&input, &bad, VerifyPolicy::default()).is_verified());
240    }
241
242    #[test]
243    fn artifact_verification_accepts_a_learned_table_and_rejects_garbage() {
244        let triples = vec![(0, 0, 1), (2, 0, 3)];
245        let cfg = TrainConfig {
246            model: ScoreModel::TransE { p: 2 },
247            rank: 8,
248            epochs: 400,
249            lr: 0.05,
250            margin: 1.0,
251            reg: 0.0,
252            neg_per_pos: 4,
253            seed: 7,
254        };
255        let table = train(&triples, 4, 1, cfg).unwrap();
256        let input = JobInput::EmbeddingArtifact {
257            triples,
258            n_entities: 4,
259            n_relations: 1,
260            cfg,
261            check: vec![(0, 0, 1), (2, 0, 3)],
262        };
263        let good = JobResult::EmbeddingArtifact { table };
264        assert!(verify(&input, &good, VerifyPolicy::default()).is_verified());
265
266        // An untrained (zeroed) table cannot reproduce ranking → rejected.
267        let empty = crate::solvers::learning::kg_embedding::EmbeddingTable::zeros(
268            ScoreModel::TransE { p: 2 },
269            8,
270            4,
271            1,
272        )
273        .unwrap();
274        let garbage = JobResult::EmbeddingArtifact { table: empty };
275        assert!(!verify(&input, &garbage, VerifyPolicy::default()).is_verified());
276    }
277
278    #[test]
279    fn mismatched_kinds_rejected() {
280        let input = JobInput::DenseLinearProduct {
281            m: 1,
282            k: 1,
283            n: 1,
284            a: vec![1.0],
285            b: vec![1.0],
286        };
287        let table = crate::solvers::learning::kg_embedding::EmbeddingTable::zeros(
288            ScoreModel::TransE { p: 2 },
289            2,
290            2,
291            1,
292        )
293        .unwrap();
294        let wrong = JobResult::EmbeddingArtifact { table };
295        assert!(!verify(&input, &wrong, VerifyPolicy::default()).is_verified());
296    }
297}