Theory Queue

Error bounds and analyses, in the order Doc 03 §8 queues them. Each section states its claim, its derivation, and the simulation that validates it.

Status: items 1, 2, 6 derived and simulation-validated (evidence: results/d2sim-primary-m3-20260731-193030.csv + .log, see also Document 04). Items 3–5 remain queue-only — genuinely separate future work, not touched by the D2 harness. Item 6’s mixing-function-level gap (spec.Finalize’s avalanche property, §6 below) is closed as of 2026-08-03: internal/spec/eviction_test.go now unit-tests it directly, alongside ScheduleM3.

1. Chip-mask schedule vs HeavyKeeper `b^(−count)`: protection curve + admission-time bound

Claim: Schedule M3 reproduces Option C’s protection curve closely enough that aggregate outcomes are statistically indistinguishable from Option C across every tested traffic/pressure combination — and specifically, Option A’s admission time for a new elephant never exceeds Option C’s own observed range, in any of the 15 combinations tested; in 8 of them it is strictly faster.

Derivation. Doc 03.2 §2–3 already worked out the conversion on paper: target p = 1.08^(−eff), M3 computes k = (eff × 227) >> 11 ≈ eff / 9 (fixed-point fit of log₂(1.08) ≈ 0.111), chip probability p_A = 2^(−k). The two curves track within ~7% of each other at moderate eff (e.g. eff = 100: p_A ≈ 4.88×10⁻⁴ vs p_C ≈ 4.54×10⁻⁴) — but they are not identical everywhere, and the gap has a predictable shape and sign:

For eff ≲ 9, k rounds down to 0, so p_A = 1.0 — M3 always wins the challenge against very weak occupants. Option C’s curve over that same range is smooth and strictly below 1.0 (p_C(1) ≈ 0.926 down to p_C(8) ≈ 0.540).
Weak, low-eff occupants are exactly what dominates a table under real pressure (§2 below). So M3 is derivably more aggressive than C at clearing the deadweight that’s actually in contention most of the time — which mechanically predicts faster admission for a genuine newcomer, not slower. Doc 03.2 §4 logged this as “a known, benign divergence” before any simulation ran.
Above the schedule’s cap (kcap = 20, eff ≳ 300), M3 is more permissive than C, but Doc 03.2 §7’s argument is that this only governs occupants whose fate is already sealed (either genuinely alive and refilling far faster than a 1-in-2²⁰ erosion rate, or already fading out of the capped region within a handful of epochs) — elephant recall is the metric that would catch this if the argument were wrong.

Simulation validation. Across 165 gated-metric checks (11 metrics × 15 combinations, 20 seeds each):

elephant_err_p50 — the core protection-curve fidelity metric — landed inside Option C’s own band in all 300 individual measurements, zero exceptions. The curves agree closely enough that elephant tracking accuracy is not distinguishable from Option C anywhere tested.
The derived low-eff aggressiveness gap shows up directly in the diagnostic eviction_rate: Option A ran +0.073 to +0.083 higher than Option C in every one of the 15 combinations — a strikingly consistent signature, not workload-specific noise.
That consistency, translated into the metric that actually gates the decision: 8 of 165 checks had Option A’s median admission time outside Option C’s band, and 100% of those were on the faster side (0 were slower). Two worked examples, straight from the data:
- zipfian-s0.8, starved: admission_events_p99 — Option C’s 20-seed range is [18604, 34061] events; Option A’s median is 17266 — faster than Option C’s single best trial.
- churn, tight: admission_events_p99 — Option C’s range is [7834, 321111]; Option A’s median is 7379.5.

Bound, stated plainly: under every traffic shape and pressure level tested, admission_time(A) ≤ max(admission_time(C) observed range), with strict improvement in roughly half the pressure-stressed cells (all misses were at tight/starved, none at comfortable — consistent with the derivation, since the low-eff divergence only bites when weak occupants are actually being challenged).

2. Bucket overflow probability under Zipfian + churn at recommended sizing

Claim: Doc 02 §4.4’s recommended sizing formula (buckets ≥ expected_concurrent_elephants × 4 / slots_per_bucket) does not produce low eviction activity — eviction rate exceeds 97% even at “comfortable” sizing, for every traffic shape tested. It does, however, achieve its actual stated purpose: elephants survive. The formula was never meant to make the table quiet; Doc 02 §4.4 says outright “mice are allowed to collide, evaporate, and churn.” The simulation confirms that promise holds even under heavy, continuous contention.

Derivation. The sizing formula sizes capacity to expected concurrent elephant count, deliberately ignoring total key cardinality — the whole conceptual unlock heavy-hitter structures depend on. At internet-scale cardinality (this experiment used a 1,000,000-key space against a 50–400 slot table depending on pressure tier), the number of mice alone vastly exceeds capacity at every pressure tier, including “comfortable” — so Phase 3 (eviction) engages constantly regardless of tier. This was predicted analytically before the full-scale run (Step 5.5’s own sizing tests already showed >99% eviction rate at comfortable pressure at smoke scale) and is now confirmed at full scale.

Simulation validation (Option A, mean of 20 seeds, from the final run):

Pressure	buckets	eviction_rate range	elephant_recall_mean range
comfortable	50	0.978 – 0.999	0.905 – 0.996
tight	13	0.976 – 1.000	0.563 – 0.704
starved	7	0.975 – 1.000	0.360 – 0.445

Eviction rate is uniformly high across all three tiers (the “bucket overflow probability” the sizing formula’s own text flagged as needing this exact analysis is, in practice, ≈1 — overflow is the normal operating condition, not an edge case). But elephant recall — the metric that actually measures whether the sizing formula does its job — tracks pressure tier tightly and stays strong (90–99.6%) specifically at the tier the formula is meant to guarantee. The formula’s promise is about who survives contention, not about whether contention happens, and the data supports exactly that reading, not a stronger one.

The churn-specific finding (Document 04 §5), carried forward here since this item’s title names churn explicitly: Option C’s admission-time p99 tail under churn is dramatically wider than under any other traffic shape — [7834, 321111] events at tight, [9306, 2205784] at starved, roughly three orders of magnitude beyond every Zipfian/burst cell (which stay in the 4,000–15,500 range). This doesn’t change the recall/overflow picture above, but it’s a real, open signal about Option C’s own tail behavior under population rotation specifically — flagged, not yet explained (no root-cause theory exists for it yet; a candidate for follow-up analysis, not resolved here).

3. Fingerprint collision rate (16-bit, 8-way) and its estimate-inflation contribution

Status: not started. internal/experiment/workload.TagCollision exists (Doc 03 §3.4) and can construct pools of keys engineered to share both bucket and 16-bit tag, but no dedicated study has been run with it. This item needs its own harness wiring (cmd/d2sim doesn’t currently drive a TagCollision workload) and its own run, separate from the D2 matrix.

4. Zombie residual-read probability under scrub-on-write

Status: not started. Explicitly out of the D2 scope guardrail (Doc 03: “wraparound/zombie simulation… needs epoch fast-forwarding, not streams”). Requires a dedicated micro-experiment that fast-forwards the epoch counter near its wrap boundary — nothing in the current harness does this, nor should it be retrofitted into the event-stream-per-tick model the D2 harness uses.

The production engine’s own test suite now reproduces the mechanism directly (a fast-forwarded fake clock demonstrating both the ordinary defended case and the narrow exact-wrap residual window), which confirms the qualitative behavior Doc 02 §5 describes. That is not the same thing as this item’s claim: a derived, quantified residual-read probability validated by simulation. This item stays queue-only until that derivation exists.

5. Morris-counter variant analysis for slow-tick deployments

Status: not started. An alternate representation (Doc 02 §3.6, Alt B), not exercised by any existing harness — internal/experiment/sketch’s Slot (and the production engine’s packed word) only implement the ratified 16|24|24 layout. Would need its own Slot/Effective variant and its own comparison, not a natural extension of the current gate.

6. Adversarial entropy analysis of hash-derived chipping

Claim: under the entropy-attack scenario tested (adversary injects keys engineered so the low 4 bits of their spare hash bits are all zero, at 20% of traffic share, against tight/starved pressure), Option A’s elephant recall does not degrade meaningfully relative to Option C’s — the keyed-hash defense (Doc 02 §4.3, D4) is not required at this attack strength.

Derivation. Doc 03.3 §3’s draw is finalize(spare ⊕ victimWord ⊕ salt×ODD) — the adversary controls only one of three XORed ingredients (spare); victimWord is the real victim’s own state and salt is a structure-wide counter that increments on every eviction attempt, guaranteed fresh per attempt (Doc 03.3 §2.1’s static-pairing-bug fix). Even with spare’s low bits fully biased toward zero, the finalize avalanche step mixes all three ingredients together before the win-test reads any bits — the adversary’s contribution is laundered through the same mixing that protects everyone else’s. Doc 03.3 §5 is explicit that this claims testability, not immunity: “an adversary who knows the unkeyed hash function may choose keys to bias spare’s distribution… If the entropy attack defeats Option A even under a keyed hash, gate clause 4.2 sends Option C to ship.” This item is that test, run once, at one attack strength.

Simulation validation. 40 runs per option (20 seeds × 2 pressure tiers: tight, starved), entropy-attack pool of 20 keys with ZeroBits=4 mixed into a strong-skew (s=1.4) Zipfian background at a 20% adversarial share:

Option A mean elephant recall: 0.6075
Option C mean elephant recall (same adversarial traffic, unbiased by construction — Option C’s lottery doesn’t use spare hash bits at all): 0.6111
Ratio: 0.9942, against Doc 03 §4.2’s pre-registered 0.95 threshold — comfortably clear, no keyed-hash fallback invoked.

Honest scope limit: this validates one attack configuration (ZeroBits=4 of a possible 0–16 the harness supports, 20% traffic share). It is not an exhaustive sweep across attack strength — a stronger bias (ZeroBits=8+) or a higher adversarial share is untested. If a future need arises to push adversarial strength further and the ratio degrades, Doc 02 §4.3’s keyed-hash requirement remains the pre-designated, pre-approved fallback — not invoked here because it wasn’t needed at the strength tested, not because it’s been ruled unnecessary in general.

Test-coverage gap, flagged 2026-08-03, closed same day: the mechanism this item’s derivation leans on — spec.Finalize’s avalanche mixing launders an adversary’s biased spare bits before the win-test reads any of them — was previously backed only by the aggregate 40-run simulation above (the 0.9942 ratio), never by a direct unit-level test of spec.Finalize itself. internal/spec had no eviction_test.go at all: ScheduleM3 and Finalize were exercised only indirectly, via hand-computed correctness traces in eviction_test.go (root package) and internal/experiment/sketch/eviction_test.go, plus one test (TestOptionA_SaltAloneChangesDraw) that proves changing the salt alone produces a different draw — not that the output is well-mixed (bit- independent, ~50% flip rate per input-bit change). Compare internal/spec/hash_test.go’s TestHashString_AvalancheBias + TestHash_BucketDistributionChiSquare, which tested exactly this property for the hash function with no counterpart for Finalize.

Closed via internal/spec/eviction_test.go:

TestFinalize_AvalancheBias — same shape as the hash function’s test: flip one of 64 input bits, expect ~32/64 output bits to flip on average.
TestFinalize_LowBitBias_WinTestWindow — targets this item’s actual threat model more precisely: flips one of the input’s low 16 bits (the adversary’s real lever, per Doc 03.3 §5’s ZeroBits model) and checks perturbation lands in the win-test’s actual read window (draw & ((1<<k)-1), k ≤ Kcap=20), not just anywhere across all 64 output bits.
TestScheduleM3_HandComputed — spec.ScheduleM3 picked up its own direct coverage in the same pass (previously only exercised indirectly via re-exports elsewhere).

This closes the unit-test gap; it does not extend item 6’s own honest scope limit above (still one attack configuration, not an exhaustive sweep).