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

qualia_core_db/services/swarm/
verify.rs
