sketch_cusum_vs_threshold_bench.nx source
↩ module page · 99 lines · 3928 B
1// sketch_cusum_vs_threshold_bench.nx -- change-point detection bench.
2//
3// CLAIM TO VALIDATE:
4// CUSUM (Page 1954) detects a SHIFT in stream mean faster and with
5// fewer false alarms than a single-threshold rule. Threshold-only
6// alerts when ANY sample crosses the threshold -- prone to false
7// positives from natural noise. CUSUM accumulates evidence over
8// multiple samples, so it triggers only on persistent drift.
9//
10// WORKLOAD:
11// - Phase 1 (steps 1..100): samples ~ N(100, 5) -- normal regime
12// - Phase 2 (steps 101..200): samples ~ N(120, 5) -- shifted mean
13//
14// Threshold = 115 (between the two means).
15//
16// MEASUREMENT:
17// CUSUM: count detections in Phase 1 (false alarms) vs Phase 2.
18// Threshold: same.
19// Score = (correct detections in Phase 2) - (false alarms in Phase 1).
20// Higher wins.
21
22import "syscalls.nx"
23import "sketch_cusum.nx"
24import "sketch_comparator.nx"
25import "sketch_types.nx"
26
27const NX_CUB_LCG_A: i64 = 1103515245
28const NX_CUB_LCG_C: i64 = 12345
29const NX_CUB_LCG_MOD: i64 = 0x7FFFFFFF
30
31func main() -> i64 {
32 // k = reference mean = 100, delta = 5 (slack), h = 10 (alarm threshold for accumulator).
33 let cs: *Cusum = nx_cusum_alloc(100, 5, 10)
34 if cs == (0 as *Cusum) { return __syscall(93, 1, 0, 0, 0, 0, 0) }
35
36 let threshold_val: i64 = 115 // baseline threshold rule
37
38 var sim: i64 = 7
39 var cusum_alarms_p1: i64 = 0
40 var cusum_alarms_p2: i64 = 0
41 var thresh_alarms_p1: i64 = 0
42 var thresh_alarms_p2: i64 = 0
43
44 // ---- Phase 1: stationary mean = 100 ----
45 var t: i64 = 1
46 while t <= 100 {
47 sim = ((sim * NX_CUB_LCG_A) + NX_CUB_LCG_C) & NX_CUB_LCG_MOD
48 // mean=100, jitter +-5
49 let jitter: i64 = (sim & 0x1F) - 16 // -16..+15
50 let value: i64 = 100 + jitter / 3 // -5..+5
51 let prev_alarms: i64 = nx_cusum_n_alarms(cs)
52 nx_cusum_add(cs, value)
53 let new_alarms: i64 = nx_cusum_n_alarms(cs)
54 if new_alarms > prev_alarms { cusum_alarms_p1 = cusum_alarms_p1 + 1 }
55 if value >= threshold_val { thresh_alarms_p1 = thresh_alarms_p1 + 1 }
56 t = t + 1
57 }
58
59 // ---- Phase 2: shifted mean = 120 ----
60 t = 1
61 while t <= 100 {
62 sim = ((sim * NX_CUB_LCG_A) + NX_CUB_LCG_C) & NX_CUB_LCG_MOD
63 let jitter: i64 = (sim & 0x1F) - 16
64 let value: i64 = 120 + jitter / 3
65 let prev_alarms: i64 = nx_cusum_n_alarms(cs)
66 nx_cusum_add(cs, value)
67 let new_alarms: i64 = nx_cusum_n_alarms(cs)
68 if new_alarms > prev_alarms { cusum_alarms_p2 = cusum_alarms_p2 + 1 }
69 if value >= threshold_val { thresh_alarms_p2 = thresh_alarms_p2 + 1 }
70 t = t + 1
71 }
72
73 // ---- Scoring: detections in P2 minus false alarms in P1 ----
74 let cusum_score: i64 = cusum_alarms_p2 - cusum_alarms_p1
75 let thresh_score: i64 = thresh_alarms_p2 - thresh_alarms_p1
76
77 // ---- CUSUM should detect the shift (P2 alarms > 0) ----
78 if cusum_alarms_p2 == 0 { return __syscall(93, 10, 0, 0, 0, 0, 0) }
79
80 // ---- CUSUM false alarms in P1 should be minimal ----
81 if cusum_alarms_p1 > 5 { return __syscall(93, 20, 0, 0, 0, 0, 0) }
82
83 // ---- Threshold rule should ALSO have some P2 alarms (sanity) ----
84 if thresh_alarms_p2 == 0 { return __syscall(93, 30, 0, 0, 0, 0, 0) }
85
86 // ---- CUSUM score > threshold score (less noise, more signal) ----
87 // OR: CUSUM has materially fewer false alarms.
88 // Use cmp_memory style (smaller false alarms wins) on P1 alarm rate.
89 let cmp_fa: *ComparisonResult = nx_cmp_memory(cusum_alarms_p1 + 1, thresh_alarms_p1 + 1, 100000)
90 // CUSUM should have NO MORE false alarms than threshold (BEATS or EQUIVALENT).
91 if cmp_fa.verdict == NX_CMP_VERDICT_LOSES {
92 if cmp_fa.delta_ppm < -200000 {
93 // CUSUM has 20%+ MORE false alarms than threshold -- fail
94 return __syscall(93, 40, 0, 0, 0, 0, 0)
95 }
96 }
97
98 return 0
99}