1use std::collections::{BTreeMap, BTreeSet};
15use std::f64::consts::LN_2;
16
17use serde::{Deserialize, Serialize};
18
19use crate::error::{EvalError, Result};
20use crate::experiment::ExperimentReport;
21
22pub const STATISTICAL_REGRESSION_FORMAT_VERSION: u64 = 1;
24
25#[derive(Debug, Clone, Copy, PartialEq, Serialize, Deserialize)]
27#[serde(deny_unknown_fields)]
28pub struct StatisticalRegressionConfig {
29 pub significance_level: f64,
31 pub minimum_pass_rate_drop: f64,
33 pub minimum_pairs: usize,
35}
36
37impl StatisticalRegressionConfig {
38 pub fn new() -> Self {
40 Self {
41 significance_level: 0.05,
42 minimum_pass_rate_drop: 0.05,
43 minimum_pairs: 30,
44 }
45 }
46
47 pub fn with_significance_level(mut self, significance_level: f64) -> Result<Self> {
49 validate_significance_level(significance_level)?;
50 self.significance_level = significance_level;
51 Ok(self)
52 }
53
54 pub fn with_minimum_pass_rate_drop(mut self, minimum: f64) -> Result<Self> {
56 validate_rate("minimum pass-rate drop", minimum)?;
57 self.minimum_pass_rate_drop = minimum;
58 Ok(self)
59 }
60
61 pub fn with_minimum_pairs(mut self, minimum_pairs: usize) -> Result<Self> {
63 if minimum_pairs == 0 {
64 return statistics_error("minimum pairs must be greater than zero");
65 }
66 self.minimum_pairs = minimum_pairs;
67 Ok(self)
68 }
69
70 fn validate(&self) -> Result<()> {
71 validate_significance_level(self.significance_level)?;
72 validate_rate("minimum pass-rate drop", self.minimum_pass_rate_drop)?;
73 if self.minimum_pairs == 0 {
74 return statistics_error("minimum pairs must be greater than zero");
75 }
76 Ok(())
77 }
78}
79
80impl Default for StatisticalRegressionConfig {
81 fn default() -> Self {
82 Self::new()
83 }
84}
85
86#[derive(Debug, Clone, Copy, PartialEq, Eq, Serialize, Deserialize)]
88#[serde(rename_all = "snake_case")]
89pub enum StatisticalDecision {
90 InsufficientEvidence,
92 NoRegression,
94 Regression,
96}
97
98#[derive(Debug, Clone, PartialEq, Serialize, Deserialize)]
100#[serde(deny_unknown_fields)]
101pub struct StatisticalRegressionReport {
102 pub format_version: u64,
104 pub baseline: String,
106 pub candidate: String,
108 pub dataset_name: String,
110 pub dataset_version: String,
112 pub config: StatisticalRegressionConfig,
114 pub pairs: usize,
116 pub both_passed: usize,
118 pub both_failed: usize,
120 pub regressions: usize,
122 pub improvements: usize,
124 pub baseline_pass_rate: f64,
126 pub candidate_pass_rate: f64,
128 pub pass_rate_drop: f64,
130 pub p_value: Option<f64>,
132 pub effect_threshold_met: bool,
134 pub significance_threshold_met: bool,
136 pub decision: StatisticalDecision,
138}
139
140impl StatisticalRegressionReport {
141 pub fn to_json(&self) -> Result<String> {
143 self.validate()?;
144 Ok(serde_json::to_string_pretty(self)?)
145 }
146
147 pub fn from_json(text: &str) -> Result<Self> {
150 let header: FormatHeader = serde_json::from_str(text)?;
151 if header.format_version != STATISTICAL_REGRESSION_FORMAT_VERSION {
152 return statistics_error(format!(
153 "unsupported statistical regression format version: found {}, this build supports {}",
154 header.format_version, STATISTICAL_REGRESSION_FORMAT_VERSION
155 ));
156 }
157 let report: Self = serde_json::from_str(text)?;
158 report.validate()?;
159 Ok(report)
160 }
161
162 fn validate(&self) -> Result<()> {
163 if self.format_version != STATISTICAL_REGRESSION_FORMAT_VERSION {
164 return statistics_error(format!(
165 "unsupported statistical regression format version: found {}, this build supports {}",
166 self.format_version, STATISTICAL_REGRESSION_FORMAT_VERSION
167 ));
168 }
169 self.config.validate()?;
170 require_non_empty("baseline experiment", &self.baseline)?;
171 require_non_empty("candidate experiment", &self.candidate)?;
172 require_non_empty("dataset name", &self.dataset_name)?;
173 require_non_empty("dataset version", &self.dataset_version)?;
174
175 let counted_pairs = self
176 .both_passed
177 .checked_add(self.both_failed)
178 .and_then(|count| count.checked_add(self.regressions))
179 .and_then(|count| count.checked_add(self.improvements))
180 .ok_or_else(|| EvalError::Statistics("pair counts overflow usize".to_owned()))?;
181 if self.pairs != counted_pairs {
182 return statistics_error("pair count does not match the outcome counts");
183 }
184
185 let expected_baseline_rate = rate(self.both_passed + self.regressions, self.pairs);
186 let expected_candidate_rate = rate(self.both_passed + self.improvements, self.pairs);
187 let expected_drop = paired_pass_rate_drop(self.regressions, self.improvements, self.pairs);
188 if !same_statistic(self.baseline_pass_rate, expected_baseline_rate)
189 || !same_statistic(self.candidate_pass_rate, expected_candidate_rate)
190 || !same_statistic(self.pass_rate_drop, expected_drop)
191 {
192 return statistics_error("reported pass rates do not match the paired outcomes");
193 }
194
195 let expected_effect = effect_threshold_met(
196 self.regressions,
197 self.improvements,
198 self.pairs,
199 self.config.minimum_pass_rate_drop,
200 );
201 let expected_log_p = (self.pairs >= self.config.minimum_pairs).then(|| {
202 exact_binomial_upper_log_tail(self.regressions + self.improvements, self.regressions)
203 });
204 let expected_p = expected_log_p.map(display_p_value);
205 if !same_optional_statistic(self.p_value, expected_p) {
206 return statistics_error("reported p-value does not match the paired outcomes");
207 }
208 let expected_significance = expected_log_p
209 .map(|value| log_probability_at_or_below(value, self.config.significance_level.ln()))
210 .unwrap_or(false);
211 let expected_decision = statistical_decision(
212 self.pairs,
213 &self.config,
214 expected_effect,
215 expected_significance,
216 );
217 if self.effect_threshold_met != expected_effect
218 || self.significance_threshold_met != expected_significance
219 || self.decision != expected_decision
220 {
221 return statistics_error("statistical decision does not match its evidence");
222 }
223 Ok(())
224 }
225}
226
227#[derive(Deserialize)]
228struct FormatHeader {
229 format_version: u64,
230}
231
232pub fn detect_pass_rate_regression(
239 baseline: &ExperimentReport,
240 candidate: &ExperimentReport,
241 config: &StatisticalRegressionConfig,
242) -> Result<StatisticalRegressionReport> {
243 config.validate()?;
244 validate_input_report("baseline", baseline)?;
245 validate_input_report("candidate", candidate)?;
246
247 if baseline.dataset_name != candidate.dataset_name
248 || baseline.dataset_version != candidate.dataset_version
249 {
250 return statistics_error(format!(
251 "reports must use the same dataset version; baseline is {}@{}, candidate is {}@{}",
252 baseline.dataset_name,
253 baseline.dataset_version,
254 candidate.dataset_name,
255 candidate.dataset_version
256 ));
257 }
258 if baseline.runs_per_case != candidate.runs_per_case {
259 return statistics_error(format!(
260 "reports must use the same runs_per_case; baseline is {}, candidate is {}",
261 baseline.runs_per_case, candidate.runs_per_case
262 ));
263 }
264
265 let baseline_runs = run_outcomes("baseline", baseline)?;
266 let candidate_runs = run_outcomes("candidate", candidate)?;
267 require_identical_keys(&baseline_runs, &candidate_runs)?;
268
269 let mut both_passed = 0;
270 let mut both_failed = 0;
271 let mut regressions = 0;
272 let mut improvements = 0;
273 for (key, baseline_passed) in &baseline_runs {
274 let candidate_passed = candidate_runs[key];
275 match (*baseline_passed, candidate_passed) {
276 (true, true) => both_passed += 1,
277 (false, false) => both_failed += 1,
278 (true, false) => regressions += 1,
279 (false, true) => improvements += 1,
280 }
281 }
282
283 let pairs = baseline_runs.len();
284 let baseline_pass_rate = rate(both_passed + regressions, pairs);
285 let candidate_pass_rate = rate(both_passed + improvements, pairs);
286 let pass_rate_drop = paired_pass_rate_drop(regressions, improvements, pairs);
287 let effect_threshold_met = effect_threshold_met(
288 regressions,
289 improvements,
290 pairs,
291 config.minimum_pass_rate_drop,
292 );
293
294 let log_p_value = (pairs >= config.minimum_pairs)
295 .then(|| exact_binomial_upper_log_tail(regressions + improvements, regressions));
296 let p_value = log_p_value.map(display_p_value);
297 let significance_threshold_met = log_p_value
298 .map(|value| log_probability_at_or_below(value, config.significance_level.ln()))
299 .unwrap_or(false);
300 let decision = statistical_decision(
301 pairs,
302 config,
303 effect_threshold_met,
304 significance_threshold_met,
305 );
306
307 Ok(StatisticalRegressionReport {
308 format_version: STATISTICAL_REGRESSION_FORMAT_VERSION,
309 baseline: baseline.name.clone(),
310 candidate: candidate.name.clone(),
311 dataset_name: baseline.dataset_name.clone(),
312 dataset_version: baseline.dataset_version.clone(),
313 config: *config,
314 pairs,
315 both_passed,
316 both_failed,
317 regressions,
318 improvements,
319 baseline_pass_rate,
320 candidate_pass_rate,
321 pass_rate_drop,
322 p_value,
323 effect_threshold_met,
324 significance_threshold_met,
325 decision,
326 })
327}
328
329type RunKey = (String, usize);
330
331fn run_outcomes(label: &str, report: &ExperimentReport) -> Result<BTreeMap<RunKey, bool>> {
332 let mut outcomes = BTreeMap::new();
333 let mut case_ids = BTreeSet::new();
334 for case in &report.cases {
335 if case.case_id.trim().is_empty() {
336 return statistics_error(format!("{label} report contains an empty case id"));
337 }
338 if !case_ids.insert(case.case_id.as_str()) {
339 return statistics_error(format!(
340 "{label} report contains duplicate case id `{}`",
341 case.case_id
342 ));
343 }
344 if case.runs.len() != report.runs_per_case {
345 return statistics_error(format!(
346 "{label} case `{}` has {} runs; expected {}",
347 case.case_id,
348 case.runs.len(),
349 report.runs_per_case
350 ));
351 }
352 for run in &case.runs {
353 if run.repetition >= report.runs_per_case {
354 return statistics_error(format!(
355 "{label} case `{}` has out-of-range repetition {}",
356 case.case_id, run.repetition
357 ));
358 }
359 let key = (case.case_id.clone(), run.repetition);
360 if outcomes.insert(key.clone(), run.passed).is_some() {
361 return statistics_error(format!(
362 "{label} report contains duplicate run `{}#{}`",
363 key.0, key.1
364 ));
365 }
366 }
367 }
368 Ok(outcomes)
369}
370
371fn require_identical_keys(
372 baseline: &BTreeMap<RunKey, bool>,
373 candidate: &BTreeMap<RunKey, bool>,
374) -> Result<()> {
375 if baseline.keys().eq(candidate.keys()) {
376 return Ok(());
377 }
378 if let Some((case_id, repetition)) = baseline.keys().find(|key| !candidate.contains_key(*key)) {
379 return statistics_error(format!(
380 "candidate report is missing paired run `{case_id}#{repetition}`"
381 ));
382 }
383 if let Some((case_id, repetition)) = candidate.keys().find(|key| !baseline.contains_key(*key)) {
384 return statistics_error(format!(
385 "baseline report is missing paired run `{case_id}#{repetition}`"
386 ));
387 }
388 statistics_error("reports do not contain identical paired runs")
389}
390
391fn validate_input_report(label: &str, report: &ExperimentReport) -> Result<()> {
392 crate::gate::validate_report(report)
393 .map_err(|error| EvalError::Statistics(format!("{label} report is invalid: {error}")))
394}
395
396#[cfg(test)]
402fn exact_binomial_upper_tail(discordant: usize, regressions: usize) -> f64 {
403 display_p_value(exact_binomial_upper_log_tail(discordant, regressions))
404}
405
406fn exact_binomial_upper_log_tail(discordant: usize, regressions: usize) -> f64 {
407 if discordant == 0 || regressions == 0 {
408 return 0.0;
409 }
410
411 let mode = discordant / 2;
412 let max_index = regressions.max(mode);
413 let max_log_mass = log_binomial_mass(discordant, max_index);
414 let mut log_mass = log_binomial_mass(discordant, regressions);
415 let mut scaled_sum = 0.0;
416 for k in regressions..=discordant {
417 scaled_sum += (log_mass - max_log_mass).exp();
418 if k < discordant {
419 log_mass += ((discordant - k) as f64).ln() - ((k + 1) as f64).ln();
420 }
421 }
422
423 let log_tail = max_log_mass + scaled_sum.ln();
424 log_tail.min(0.0)
425}
426
427fn display_p_value(log_p_value: f64) -> f64 {
428 const MIN_SUBNORMAL: f64 = f64::from_bits(1);
429 if log_p_value >= 0.0 {
430 1.0
431 } else {
432 log_p_value.exp().max(MIN_SUBNORMAL)
433 }
434}
435
436fn log_binomial_mass(trials: usize, successes: usize) -> f64 {
437 let factors = successes.min(trials - successes);
438 let mut log_choose = 0.0;
439 for i in 1..=factors {
440 log_choose += ((trials - factors + i) as f64).ln() - (i as f64).ln();
441 }
442 log_choose - trials as f64 * LN_2
443}
444
445fn validate_rate(label: &str, value: f64) -> Result<()> {
446 if !value.is_finite() || !(0.0..=1.0).contains(&value) {
447 return statistics_error(format!("{label} must be a finite number in 0.0..=1.0"));
448 }
449 Ok(())
450}
451
452fn rate(passed: usize, pairs: usize) -> f64 {
453 if pairs == 0 {
454 0.0
455 } else {
456 passed as f64 / pairs as f64
457 }
458}
459
460fn paired_pass_rate_drop(regressions: usize, improvements: usize, pairs: usize) -> f64 {
461 if pairs == 0 {
462 0.0
463 } else {
464 (regressions as f64 - improvements as f64) / pairs as f64
465 }
466}
467
468fn effect_threshold_met(
469 regressions: usize,
470 improvements: usize,
471 pairs: usize,
472 minimum_drop: f64,
473) -> bool {
474 regressions > improvements
475 && paired_pass_rate_drop(regressions, improvements, pairs) >= minimum_drop
476}
477
478fn statistical_decision(
479 pairs: usize,
480 config: &StatisticalRegressionConfig,
481 effect_threshold_met: bool,
482 significance_threshold_met: bool,
483) -> StatisticalDecision {
484 if pairs < config.minimum_pairs {
485 StatisticalDecision::InsufficientEvidence
486 } else if effect_threshold_met && significance_threshold_met {
487 StatisticalDecision::Regression
488 } else {
489 StatisticalDecision::NoRegression
490 }
491}
492
493fn same_statistic(actual: f64, expected: f64) -> bool {
494 if !actual.is_finite() || !expected.is_finite() {
495 return false;
496 }
497 if actual == expected {
498 return true;
499 }
500 let scale = actual.abs().max(expected.abs());
501 (actual - expected).abs() <= 16.0 * f64::EPSILON * scale
502}
503
504fn same_optional_statistic(actual: Option<f64>, expected: Option<f64>) -> bool {
505 match (actual, expected) {
506 (Some(actual), Some(expected)) => same_statistic(actual, expected),
507 (None, None) => true,
508 _ => false,
509 }
510}
511
512fn log_probability_at_or_below(actual: f64, threshold: f64) -> bool {
513 if actual <= threshold {
514 return true;
515 }
516 let scale = actual.abs().max(threshold.abs()).max(1.0);
517 actual - threshold <= 16.0 * f64::EPSILON * scale
518}
519
520fn require_non_empty(label: &str, value: &str) -> Result<()> {
521 if value.trim().is_empty() {
522 return statistics_error(format!("{label} must not be empty"));
523 }
524 Ok(())
525}
526
527fn validate_significance_level(value: f64) -> Result<()> {
528 if !value.is_finite() || value <= 0.0 || value >= 1.0 {
529 return statistics_error(
530 "significance level must be a finite number strictly between 0 and 1",
531 );
532 }
533 Ok(())
534}
535
536fn statistics_error<T>(message: impl Into<String>) -> Result<T> {
537 Err(EvalError::Statistics(message.into()))
538}
539
540#[cfg(test)]
541mod tests {
542 use super::*;
543
544 #[test]
545 fn exact_known_upper_tails() {
546 assert_eq!(exact_binomial_upper_tail(0, 0), 1.0);
547 assert_eq!(exact_binomial_upper_tail(5, 5), 0.03125);
548 assert!((exact_binomial_upper_tail(10, 8) - 0.054_687_5).abs() < 1e-14);
549 assert_eq!(exact_binomial_upper_tail(10, 0), 1.0);
550 }
551
552 #[test]
553 fn exact_tail_stays_finite_for_large_samples() {
554 let tiny = exact_binomial_upper_tail(10_000, 10_000);
555 assert!(tiny.is_finite());
556 assert!(tiny > 0.0);
557 assert!(tiny <= f64::MIN_POSITIVE);
558
559 let balanced = exact_binomial_upper_tail(10_000, 5_000);
560 assert!(balanced > 0.5 && balanced < 0.51, "{balanced}");
561 }
562}