nitro_batch_countmin_error_bound_zipf is vacuous: an estimator returning 0 for every key passes it

[GordonYuanyc]

Summary

nitro_batch_countmin_error_bound_zipf (src/sketch_framework/nitro.rs:341) cannot fail for any sampling-calibration bug. Its error bound is larger than the true count of ~98% of the keys it checks, so an estimator that returns 0 for every key passes it.

This is where the three Nitro bugs fixed in #82 were hiding.

The arithmetic

The test uses rows = 3, cols = 4096, domain = 8192, exponent = 1.1, samples = 200_000, and asserts:

let epsilon = std::f64::consts::E / cols as f64;
let delta = 1.0 / std::f64::consts::E.powi(rows as i32);
let error_bound = epsilon * samples as f64;              // = 132.73
let correct_lower_bound = truth.len() as f64 * (1.0 - delta);   // = truth.len() * 0.9502
// ... within_count counts keys with |est - truth| < error_bound
// then asserts within_count >= correct_lower_bound

Under Zipf(1.1) over 8192 keys with 200_000 samples, the expected count of the rank-i key is samples / (H * i^1.1) with H = Σ 1/i^1.1. Counting keys whose expected count reaches the bound:

error_bound                              = 132.73
keys with expected count >= error_bound  = 140 of 8192  (1.71%)
=> an estimator returning 0 for EVERY key scores 98.29% within-bound
   threshold is 95.02%                    => PASSES

Only the ~140 head keys can ever exceed the bound; the 8052-key tail has true counts below 132.73, so |0 - truth| < 132.73 holds for them regardless of what the sketch does.

Why this matters

Three separate calibration bugs lived behind this green test (all found by #82, independently reproduced here):

1. CountMin::fast_insert_nitro underflow-panicked at rate == 1.0
2. Nitro::draw_geometric ignored the configured sampling_rate entirely — achieved density was a constant ~4.35% at every configured rate
3. an off-by-one made the achieved density p/(1+p) instead of p

None of them could move this test's needle, because none of them affect the 8052 tail keys enough to cross a 132.73-unit bound.

Suggested replacement

An accuracy test for a sampling sketch has to be sensitive to the sampling rate. Concretely:

1. Sweep the rate. [1.0, 0.5, 0.1, 0.05, 0.02, 0.01], not just the default. Bugs 1 and 3 above are only visible off-default.
2. Assert relative error on head keys, not absolute error on all keys. The tail is where the bound goes vacuous.
3. Test achieved sampling density directly, separately from the estimate. If delta and the skip distribution are both wrong they can partially cancel in an estimate test but not in a density test.

Sketch of (3), which is what caught bug 2 here:

let mut sketch = CountMin::<Vector2D<i32>, FastPath>::with_dimensions(1, 4096);
sketch.enable_nitro(rate);
for i in 0..inserts as u64 {
    sketch.fast_insert_nitro(&DataInput::U64(i));
}
// every applied update adds exactly `delta`, so total/delta = updates applied
let applied = total_matrix_sum(&sketch) / sketch.as_storage().get_delta() as f64;
let achieved = applied / inserts as f64;
assert!((achieved - rate).abs() / rate < 0.10);

Before #82 this reports 0.0435 for every one of rate = 0.5, 0.1, 0.05, 0.02 — the same number four times, which is the signature of a sampler ignoring its configured rate. After #82 it passes.

Scope

Worth auditing the other error-bound tests for the same shape — an absolute epsilon * N bound checked against a heavy-tailed key distribution is vacuous for the tail whenever epsilon * N exceeds typical tail counts.