1use super::job::{JobInput, JobResult};
14use crate::solvers::linear_algebra::gemm::{matvec, Transpose};
15use crate::solvers::optimization::metaheuristics::Rng;
16
17#[derive(Debug, Clone, Copy, PartialEq)]
19pub enum VerificationVerdict {
20 Verified { confidence: f64 },
22 Rejected { reason: &'static str },
24}
25
26impl VerificationVerdict {
27 pub fn is_verified(&self) -> bool {
29 matches!(self, VerificationVerdict::Verified { .. })
30 }
31}
32
33#[derive(Debug, Clone, Copy)]
35pub struct VerifyPolicy {
36 pub freivalds_rounds: usize,
38 pub tol: f64,
40 pub seed: u64,
42 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
57pub 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
80fn 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 for xi in x.iter_mut() {
98 *xi = if rng.unit() < 0.5 { -1.0 } else { 1.0 };
99 }
100 if matvec(Transpose::No, k, n, b, &x, &mut bx).is_err() {
102 return VerificationVerdict::Rejected {
103 reason: "reference matvec failed",
104 };
105 }
106 if matvec(Transpose::No, m, k, a, &bx, &mut abx).is_err() {
108 return VerificationVerdict::Rejected {
109 reason: "reference matvec failed",
110 };
111 }
112 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
130fn 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 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 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 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 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; 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 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}