03 · D2 Experiment Plan

Purpose: unblock decision D2 (eviction mechanism: §4.1 Option A hash-entropy chipping vs Option C HeavyKeeper-classic RNG). Discipline: this plan is written and frozen before the harness produces a single number. Anything we change after seeing results gets logged in a “Deviations” appendix — visible, not silent. Scope guardrail: D2 is an accuracy question. Everything here is single-threaded, correctness-oriented simulation. Concurrency, CAS, throughput, and SIMD are explicitly out of scope for this step.

---

Step 0 — Freeze the two contestants (paper work, no code)

• 0.1 Write the exact algorithm of Option C (HeavyKeeper-classic) as adapted to our word layout: victim = min-effective slot; decrement with probability b^(−victim.count); parameter b (paper default ≈ 1.08). This is the literature baseline — it must be implemented faithfully, not charitably.
• 0.2 Design candidate chip-mask schedules for Option A. The mask must approximate a geometric protection curve using only integer ops on hash bits. Define 2–3 candidates, e.g.:
  • M1: maskWidth = min(victim.count >> 3, 16) (linear-stepped)
  • M2: maskWidth = min(bitlen(victim.count), 20) (logarithmic — chip prob ≈ 1/victim.count)
  • M3: piecewise table tuned to match 1.08^−count at key points For each: tabulate implied chip probability at victim counts {1, 3, 10, 100, 1000, 10000} next to Option C’s curve. The schedule is chosen on paper first; the simulation validates, it does not search. (Searching = overfitting our own gate.)
• 0.3 Specify the entropy source precisely: which spare hash bits, how mixed with the victim word, what happens when the same key retries (does the draw change? — yes, victim word churns; write down why that’s sufficient).

Step 1 — Define ground truth (the oracle)

• 1.1 Two oracles, not one — this is the key methodological decision:
  • Oracle-S (spec semantics): exact map[key] implementation of the spec’s quantized epoch-halving decay with unlimited memory and no eviction. Comparing the sketch against Oracle-S isolates collision + eviction error — the only thing D2 is about.
  • Oracle-I (ideal): continuous exponential decay, exact. Sketch-vs-Oracle-I measures total approximation error (includes decay quantization). Reported for context; not part of the D2 gate.
• 1.2 Oracle correctness tests before anything else: hand-computed tiny cases (5 keys, 3 epochs, verify every intermediate value), plus property tests (decay monotonicity; evaporation after 24 silent epochs; count conservation absent decay). The oracle is the constitution — if it’s wrong, every result is fiction.

Step 2 — Define the metrics (what “error” means)

• 2.1 Estimate-level: relative error (estimate − truth) / truth per observation, split by key class (elephant / middle / mouse, defined by ground-truth rank). Reported as full CDFs, not just means — the tails are where designs differ.

🧭 In plain terms: take every (estimate, truth) pair the sketch ever produces, sort them into elephant/middle/mouse buckets by how big the key truly was, and keep the full sorted list of errors per bucket — not just the average — so the worst cases for big keys vs. small keys can be inspected separately. It does not ask “did the sketch know about this key at all” (that’s 2.2) — only “given that the sketch answered, how good was the number.”

Worked example. Oracle-S says five keys currently stand at:

Key	True count	Rank	Class
user_A	1000	1	elephant
user_B	800	2	elephant
user_C	50	3	middle
user_D	12	4	middle
user_E	2	5	mouse

The sketch is asked for the same five keys and answers 970, 820, 45, 15, 9. Relative error (estimate−truth)/truth per key: −0.03, +0.025, −0.10, +0.25, +3.5. Each value is filed into its class’s CDF via ClassifiedErrors.Record(class, estimate, truth). Do this across the whole stream (millions of events, not five) and the result is three separate distributions — elephant, middle, mouse — queryable by quantile (CDF.Quantile(0.99), etc.).

The user_E row is the one to watch: a mouse whose estimate is 3.5× truth is a >2× inflation — exactly the C5 (safe error direction, Doc 01 §5) violation the mouse-inflation metric (2.2) is built to catch systematically. 2.1 is what makes that single bad row visible in the first place, buried among millions of good ones.

• 2.2 Decision-level (what consumers actually feel):
  • Elephant recall: fraction of true top-K keys tracked at any instant.
  • New-elephant admission time: #events (and #epochs) from a key’s first appearance to stable tracking — the metric that exposes the v1 lockout bug; Option A must beat strict-comparison’s pathological value and match Option C.
  • Mouse inflation rate: fraction of mouse observations whose estimate exceeds truth by >2× (C5 violation proxy).
  • First-sighting flag accuracy: false-negative rate of the flag vs Oracle-S.

🧭 In plain terms: 2.1 only scores accuracy when the sketch answers. It’s blind to bigger failures like “the sketch never even noticed this key” or “the flag missed a genuine first-timer.” 2.2 is about consequences a real consumer would notice.

Worked examples.

• Elephant recall. True top-4 elephants are A, B, C, D. The sketch currently holds live slots for A, B only (C, D got evicted). Recall = 2/4 = 0.5 for this instant. Checked repeatedly across a run, this becomes a distribution — did recall ever crater to 0.2? Did it recover?

• New-elephant admission time. Key viral_post first appears at event 100. It grabs a slot, loses it, grabs it again… and finally holds a slot continuously starting at event 106. Admission time = 6 events. This is the metric built specifically to catch the v1 lockout bug — an earlier eviction design where a new elephant couldn’t get a slot until the old occupant decayed all the way to zero (up to 24 epochs). Low admission time means the sketch reacts fast to new hot keys.

• Mouse inflation rate. Across 1000 mouse observations, 50 got an estimate more than 2× their true count (a hash collision made a one-off key look busy). Inflation rate = 50/1000 = 5% — the same C5 failure mode the user_E row exposed in the 2.1 example, now measured systematically across the whole run.

• First-sighting flag accuracy. Across 200 true first-sightings (per Oracle-S), the sketch’s own flag missed 10 of them. False-negative rate = 10/200 = 5%. This matters because a consumer relies on that flag to “never go fully blind” (Doc 01 §5) — a missed flag means a genuinely new thing gets silently treated as old news.

• 2.3 Structural health: eviction rate, chip rate, slot-churn rate (sanity numbers that explain why an accuracy difference appears).

🧭 In plain terms: these three numbers don’t feed the pass/fail gate at all (§4.1 checks 2.1 and 2.2 only). They exist purely so that if Option A loses to Option C on accuracy, there’s a diagnosis instead of a shrug — what was the eviction machinery actually doing under the hood?

Worked examples.

• Eviction rate. Of 500 insert attempts into full buckets, 200 actually evicted the current occupant (the rest lost the lottery and the newcomer was turned away). Eviction rate = 200/500 = 40%.
• Chip rate. Of 1000 lottery draws against a victim slot (Option A’s hash-bit draw, or Option C’s RNG draw), 300 landed and decremented the victim. Chip rate = 30%. If Option A’s chip rate runs far hotter than Option C’s on the same workload, that’s a concrete “A is chipping too aggressively” explanation for a recall or admission-time miss in 2.2.
• Slot-churn rate. Of 800 touches on occupied slots, 500 found a different key occupying the slot than last time. Churn rate = 500/800 = 62.5% — a high-churn table is exactly what would explain a bad admission-time or recall number from 2.2.

One-line summary of the whole step: 2.1 asks “how good was the number,” 2.2 asks “did the sketch make the right call when it mattered,” and 2.3 asks “what was going on mechanically that explains the answers to the first two.”

Step 3 — Define the workloads (seeded, reproducible)

• 3.1 Zipfian family: s ∈ {0.8, 1.1, 1.4}, key space 1M, stream length ≥ 50M events.
• 3.2 Churn: Zipfian with key-population rotation (x% of keys retired/born per epoch) — the “mice churn forever” reality.
• 3.3 Burst / regime change: stable Zipfian, then a brand-new key jumps to top-1 instantly (feeds metric 2.2 admission time); also a former elephant going silent (decay recovery).
• 3.4 Adversarial:
  • Bucket flood: keys engineered to hash to one bucket (simulated via constrained hashing) — overflow pressure.
  • Entropy attack (Option A specific): adversary selects keys whose spare hash bits are biased (all-zeros region) to rig the chip lottery. This is the workload most likely to kill Option A — it goes in because of that, not despite it.
  • Tag-collision injection: forced 16-bit fingerprint collisions (feeds THEORY item 3 while we’re here).

Step 4 — Pre-register the acceptance criteria (the actual gate)

• 4.1 Primary: on every non-adversarial workload × pressure combination, Option A’s error CDFs (2.1) and decision metrics (2.2) fall within the seed-to-seed variance band of Option C (≥20 seeds each; band = Option C’s own min–max across seeds). Rationale: “indistinguishable from C” operationalized without p-value games — A must look like another seed of C.
• 4.2 Adversarial clause: under the entropy attack, Option A may degrade, but elephant recall must stay ≥ 95% of Option C’s, or the keyed-hash requirement (§4.3) must demonstrably restore parity. Document which.
• 4.3 Tie-breaker is pre-decided: if A passes, A ships (it’s cheaper — no RNG). If A fails any clause, C ships, no renegotiation in-flight. Renegotiation happens, if ever, in a v3 spec with this experiment as evidence.

Step 5 — Build order (the actual harness)

• 5.1 Repo scaffold: epochsketch/ Go module; internal/oracle, internal/sketch (single-threaded core, eviction as a pluggable function — plain function value, this is simulation code, boxing is fine here), internal/workload, cmd/d2sim.
• 5.2 Determinism everywhere: every run fully described by (workload, params, seed); PRNG is seeded rand.New per component, never global; output row records the full tuple → any result reproducible from its CSV line.
• 5.3 Output: CSV per run (metrics) + CDF dumps; plotting via a tiny script or Go — presentation is secondary, reproducibility is primary.
• 5.4 Tests before results: oracle tests (1.2), sketch unit tests on hand-computed micro-cases (one bucket, forced evictions, verify each chip/claim against manual arithmetic), golden-stream test (fixed seed → byte-identical metrics across runs and machines), and the dead ≡ empty equivalence property: any slot at effective count 0 must be observationally indistinguishable from an empty slot across every operation — same estimates, same flags, same recycling outcome (origin: design review of lingering decayed-to-zero entries; the tombstone/lazy-deletion argument must be enforced, not just asserted).
• 5.5 Table pressure: run every workload at 3 table sizes — comfortable (elephants ≪ capacity), tight (≈ capacity), starved (elephants > capacity). If the table is never under pressure, both options look identical and the experiment is void. (Moved from §3.5 — capacity is a property of internal/sketch, which doesn’t exist until this step, so table-pressure sizing can’t be pinned down until the sketch’s own capacity knob is real.)
• 5.6 Run matrix + memo: execute the full matrix (every workload × every table-pressure size × ≥20 seeds); write Document 04: D2 Decision Memo — verdict, CDF plots, deviations appendix, and the chip-schedule choice (M1/M2/M3) if A wins.

---

Explicitly out of scope (resist the temptation)

Concurrency and CAS behavior; wraparound/zombie simulation (separate micro-experiment for §5, needs epoch fast-forwarding, not streams); throughput benchmarks; memory layout realism (the sim may use structs, not packed words — semantics are under test, not bytes); Morris-counter variant; SIMD anything.

Parking lot — named post-D2 experiments (ideas preserved, not smuggled in):

• E2: Age tie-break in nomination (LRU-within-LFU). Proposal from design review: among slots tied at minimum effective count, evict the oldest — recovering ordering that decay quantization (count >> age) discards. Analysis so far: worthless at eff 0 (dead ≡ empty; nothing to preserve), thin-but-real at eff > 0 (fresher identity ⇒ marginally likelier tag re-hit ⇒ less slot churn). Cheap composite implementation exists (score = (eff << 6) | (63 − age), single min-scan). Deciding metrics, declared now: slot-churn rate and mouse-class estimate error under churn workloads (§3.2); adopt only if both improve without hurting admission time. Runs after D2 so nomination stays a shared constant during the lottery comparison.

Deviations appendix

Logged per the header discipline: anything changed after seeing results goes here — visible, not silent.

D1 (2026-07-31) — churn workload never churned; first run’s churn cells are void

Found: all 120 churn rows in the first primary-m3 run (results/d2sim-primary-m3-20260731-151136.csv) are byte-identical to the zipfian-s1.1 rows for the same (option, seed, pressure). The §3.2 workload silently ran as plain Zipfian.

Cause: RunOnce ticked the oracle and sketch each epoch but never the workload — Churn.Tick() (the identity-rotation step) was dead code behind a generator interface that only exposes Next().

Fix: cmd/d2sim/run.go now drives any generator implementing Tick() at epoch boundaries, with a regression test (TestRunOnce_ChurnDiffersFromZipfian) asserting churn ≠ zipfian-s1.1 at equal seed. Burst was unaffected (it triggers off its own event count).

Consequence: the first run’s churn cells carry no information; the full matrix must be rerun.

D2 (2026-07-31) — §4.1 operationalization was unpassable; amended to median-in-band

Found: as implemented, §4.1 required all 20 of A’s seeds inside C’s 20-seed min–max band on all 11 gated metrics (220 all-must-pass checks per cell). Control on the run’s own data: leave-one-out, Option C fails this gate against itself in 12/12 cells (6–10 of its 20 seeds fall outside the other 19’s band every time). Theory agrees: a fresh sample lands inside the min–max of 20 priors with probability 19/21 per check, so even a true clone of C passes ≈ never. Every §4.1 FAIL in the first run is therefore uninformative, and its “ship C” verdict is void.

Amendment (this is a repair of the operationalization, not of the criterion): the pre-registered rationale — “A must look like another seed of C” — is now tested as: A’s median across seeds must fall within C’s min–max band, per gated metric, per cell. A same-distribution clone passes essentially always (both tails need ≥10 of 20 seeds beyond C’s extreme, ~1e-4 per metric); a systematic shift wider than C’s own seed variance still fails. A calibration test (TestEvaluatePrimary_Calibration_CloneOfCPasses_ShiftFails: 200 clone trials must all pass, 200 4σ-shift trials must all fail) now guards the gate itself — the control that would have caught this before the first 2h8m run. Per-seed out-of-band counts remain in the log as diagnostics.

D3 (2026-07-31, decided before the rerun — see decision at the end) — direction of the band check

Replaying the amended gate on the first run’s data (churn cells excluded as void): every cell passes except admission_events_p50/p99 in starved cells, where A-M3’s median falls below C’s band — A admits new elephants systematically faster (e.g. zipfian-s0.8 starved p99: A median 17,266 vs C band [18,604, 34,061]). §4.2 passed (recall ratio 0.9942).

So the rerun’s verdict likely hinges on one pre-registered choice:

• Two-sided (current implementation, the literal §4.1 text): out-of-band in either direction fails → C likely ships.
• One-sided for direction-unambiguous decision metrics (admission_events_* lower-better, first_sighting_fn_rate lower-better, mouse_inflation_rate lower-better, elephant_recall_mean higher-better; signed-error quantiles stay two-sided): out-of-band on the better side does not fail → A likely ships.

This choice is logged here, before fresh results exist, precisely so it cannot be made silently after them.

Decision (2026-07-31, before the rerun): one-sided for the four directional decision metrics; signed-error quantiles stay two-sided. Rationale: D2’s underlying question is “is A at least as good as C” — §4.3 ships A because it’s cheaper, so the gate exists to catch A being worse, and any hidden cost of a better-side deviation (e.g. faster admission trading off stability) is still caught by the independently gated recall, inflation, and error metrics. A better-side pass is logged explicitly in the run log and MetricResult.BetterSide — visible, not silent — so Document 04 can report “A was faster than C at admission,” not merely “A passed.”

Definition of done for this step

D2 row in the spec’s §9 table flips from “recommended, gated” to decided, with Document 04 as the evidence link — and the project has gained its permanent simulation harness, which every future THEORY.md item (§8 queue) will reuse.