Layer III sample complexity and confidence guarantees

Layer III sample complexity and confidence guarantees

This document records the sample-complexity and confidence-interval guarantees of the Layer III stochastic verifier (src/herding_cats_with_swords/layer_iii_sampler.py). Layer III estimates the rare-event probability that a loadout is a supercriticality outlier and checks it against the sparsity budget (Law 7). It is the stochastic counterpart to the Layer II compositional verifier and consumes the importance-sampling recipe established by the viability probe at docs/notes/verification/vja3-importance-sampling-probe.md.

Estimands

For each detected cycle C the verifier estimates p = P_v[ C is supercritical ], where supercriticality is gain(C, v) > theta * cost(C) (or gain > 0 when cost <= 0) under the roll distribution v. The loadout outlier probability is the union event P(any supercritical cycle) AND {eta >= 1}. Because eta (charge sustainability) is deterministic, it enters as a constant 0/1 factor. The verifier also accumulates expected_margin = E_v[ max over cycles of (gain(C, v) - theta * cost(C)) ] in the same target-distribution sampling pass; it is 0.0 when no cycles are detected.

Naive Monte Carlo sample complexity

The naive estimator draws N independent trials and reports the sample mean of the supercriticality indicator, a Bernoulli(p) statistic with per-sample variance p(1 - p). For a target relative error delta on p at 95% confidence, the Wald criterion Z * sqrt(p(1-p)/N) / p <= delta gives

N >= Z^2 * (1 - p) / (p * delta^2)  ~=  4 / (p * delta^2)

using Z ~= 1.96 and p << 1. At p ~= 1e-4 and delta = 0.10 this demands roughly 4e6 trials, which is why naive MC alone is impractical in the rare tail; at p ~= 1e-5 a budget of N = 40,000 produces a useless zero estimate.

Importance-sampling variance reduction

When the per-cycle gain is monotone in every random roll (the additive-add and multiplicative-multiply subset of Law 8) and rolls are independent (diagonal covariance), the verifier tilts each slot’s Beta proposal by an alpha-shift q_i = Beta(alpha + s, beta) and weights each trial by the per-slot Beta density ratio on the underlying unit variate x in [0, 1]. The affine rescale onto a slot’s support range commutes with the weight, so weights are computed on x directly. The tilt s auto-tunes by bisection on the proposal-hit fraction toward a target of 0.30.

The viability probe measured the variance-reduction factor (VRF), naive-MC per-sample variance divided by IS per-sample variance, for the canonical sum-of-independent-Beta gain:

Target p	VRF	N_req MC (10% rel-err)	N_req IS
1e-3	107x	428,830	3,589
1e-4	410x	3,841,075	9,233
1e-5	5985x	impractical	6,737

The VRF scales steeply with rarity, which is exactly the regime where IS pays off.

Estimator auto-switch

Importance sampling carries fixed pilot overhead (tilt tuning) and is only beneficial in the rare tail, so the verifier runs a small pilot per cycle and switches between estimators. When the pilot p_hat is at or above rare_event_switch_threshold (default 1e-3) it uses naive MC; below it, and when the IS preconditions hold, it uses tilted-Beta importance sampling. Naive MC is unbiased under any roll distribution, so the fallback is always safe.

Confidence interval and sparsity compliance

Each cycle estimate carries a Wald 95% confidence interval with half-width 1.96 * se, where se is the standard error of the (possibly importance-weighted) indicator mean. For the loadout union event the verifier reports a conservative bracket: the union bound (sum of per-cycle p_hat, capped at 1) as the upper bracket and max of per-cycle p_hat as the lower bracket, with the half-widths combined in quadrature. This is deliberately conservative; a future shared-pass estimator that samples the joint event once would yield a tighter interval (tracked as TODO(HCWS-vja.7+)). A loadout is sparsity_compliant only when exceedance is excluded at 95% confidence: outlier_probability + ci_half_width_95 <= sparsity_epsilon.

Unbiasedness-within-CI regression guard

The load-bearing correctness property is unbiasedness, not variance: a mistuned proposal or wrong weight can show tiny variance with a biased mean. The severity test test_severity_is_unbiased_and_reduces_variance (marked @pytest.mark.severity, deselected from the default just test run) calibrates an additive-add sum-of-rolls cycle to a ground-truth probability near 5e-4, then asserts the IS estimate agrees with a high-budget pilot within the combined 95% CI (|z| < 1.96) and achieves a VRF of at least 50x at N = 40,000. The measured VRF for this case is approximately 688x. This test is the HCWS-vja.9 regression guard; run it explicitly with uv run pytest -m severity.

Domain of validity

The full IS speedup holds for additive-add cycles (sum-of-independent-Beta gain), where the probe’s tilt and weights transfer verbatim. For multiplicative-multiply cycles IS remains correct (unbiased) and positive but the speedup is reduced: the transfer test test_multiplicative_transfer_is_unbiased measures a VRF of approximately 76x at p ~= 4.7e-3, confirming IS still pays off on the bilinear monotone regime, though less dramatically than the additive case. Cycles containing a non-monotone modifier op (set, min, max, or a cross layer-operation pair) void the monotonicity precondition; the verifier degrades to naive MC and emits a NON_MONOTONE_SUBSET warning. An item carrying a non-diagonal (correlated) covariance matrix likewise breaks the independent-proposal assumption; the verifier degrades to naive MC and emits a CORRELATED_ROLLS warning. Re-derivation of the tilt and weight formulas is required before IS can be applied to correlated rolls or a non-monotone gain.