| name | ecdsafail-nonce-time |
| description | How to correctly estimate the expected time to find a clean nonce for the ecdsafail circuit. Covers: empirical winner probability, GPU hunt rate, verify throughput, bottleneck analysis, and common mistakes. Use this whenever asked "how long will the hunt take?" or "how many candidates needed?" |
ecdsafail — Nonce Hunt Time Estimation
Subagent invocation: this document is run standalone by an independent subagent. After finishing the estimate, report the results (expected candidate count, expected time) back to the main agent, then shut down.
⚠️ Read this first (or you will waste hours waiting)
1. displacement / λ ≠ P_winner. Do not use a stale-nonce N_cls+N_phase (the "Theoretical prediction" table below) or λ to judge feasibility or estimate time. That is only a rough proxy, and it is only meaningful when the GPU filter is actually enriching. The only trustworthy E[time] comes from the empirical P(cls=0) measured on the current op-stream (Step 1), not from λ.
2. "I ran a measurement" ≠ "I have an estimate." If the number of cls=0 entries in the verify log is 0, you only have a lower bound, not a point estimate. In that case it is forbidden to conclude anything like "feasible, a few hours" — either keep accumulating until a cls=0 appears, or honestly report "possibly infeasible" based on the lower bound.
3. λ_residual ≈ 8.5 is not a constant. It is a value observed historically on certain circuits when the filter was well aligned. Any structural change to the circuit (especially compressed.rs or any rewrite) can throw the filter out of alignment. Never plug in 8.5 — you must re-measure it on the current circuit with Step 0.
2026-06-13 example: displacement(25.6, phase 8.6) was used to claim "at-floor, feasible in a few hours", but Step 0 measured the full-count classical of GPU-clean candidates at ≈ 19.57 (same as random nonces) → the filter was not enriching at all → e^(−8.5) invalid → the actual E[time] was unknown/possibly infeasible. displacement was the wrong proxy, and the time was wasted waiting.
Basic formula
E[time to find a winner] = E[candidates that need verifying] / min(candidate generation rate, verify rate)
= (1 / P_winner) / min(R_cand, R_verify)
Three independent variables, each measured from data. But do Step 0 first.
🚀 Staged density method (512→2048→9024 funnel) — a faster P(winner) estimate
A practice from the field ("recognize known-good nonce / candidates relatively clean / give density like 1000/100/10 at 512/2048/9024 out of 1M"). Much faster than "full 9024-shot verify for every candidate", because most candidates die at the cheap 512-shot tier and only survivors pay the expensive 9024.
Why it works (measured 2026-06-23, single fast-screen timings): cost grows with shots, it is not rebuild-only:
| NS_SHOTS | Time per run | Notes |
|---|
| 512 | ~4.4s | cheap coarse screen (~3s is fixed build overhead) |
| 2048 | ~6.4s | |
| 9024 | ~15.8s | full depth, run only for survivors |
Funnel procedure (per config, verify with DROP_DEAD_ROBUST_DISABLE=1 DROP_DEAD_ROBUST_SECOND=0 NS_EARLY_EXIT=0, because any edit shifts indices → stale .idx → fake 9024):
- GPU hunt produces candidates (classical-enriched, drop-dead-independent).
- tier-512: run candidates in parallel at NS_SHOTS=512, keep survivors with
classical=0 and phase=0.
- tier-2048: run survivors at 2048, again keep c=0∧p=0.
- tier-9024: run full depth,
0/0/0 = winner.
- density profile = N→N₅₁₂→N₂₀₄₈→N₉₀₂₄; the per-tier survival ratios give a conditional decomposition of P(winner), more accurate than a flat e^(−λ).
Key insights (measured):
- The ancilla channel is constantly 0 (non-binding) → the winner criterion effectively reduces to c=0 ∧ p=0.
- classical is enriched by the GPU filter, phase is not → phase is the real bottleneck (~e^(−⟨phase⟩)). Even if classical is pushed to 0, phase still has to independently hit 0.
- Filter recall is limited (
56%) → candidates still carry a **residual c8** at full-9024 (not 0). If the min c/p per tier does not converge toward 0 but plateaus at ~8, that λ is infeasible at the current throughput — do not grind for days, honestly report the lower bound.
- The staged verify daemon (setsid, background) polls the candidate logs of each config and runs the funnel; the first 0/0/0 is written to
/tmp/WINNER.
⚠️ A staged-funnel winner is dd-OFF (feasibility, proving the island is huntable). To be shippable it must be dd-ON: first regenerate the dead-CCX .idx for the edited stream, then dd-ON verify the same batch of candidates. The candidates themselves are drop-dead-independent and reusable.
⚠️ Step 0 (mandatory, do it first): verify the GPU filter is actually enriching
The theory P(winner) ≈ e^(−λ_residual) × … only holds when the GPU filter pushes candidates' classical significantly below random. Passing the filter alignment check (gpu mean ≤ cpu mean) only guarantees the filter is conservative (does not miss winners), not that it is selective (will enrich) — the two are completely different. A filter can be "safe but useless" (letting almost every nonce through).
Once the hunt is running and verify has produced real RESULTs, immediately do this comparison (use NS_EARLY_EXIT=0 to count the real classical count, not the early-exit 0/1 flag):
grep -h CLEAN_CANDIDATE /tmp/hunt_z3_g*.log | sed 's/.*nonce=//' | sort -un | head -40 \
| while read n; do DIALOG_TAIL_NONCE=$n NS_EARLY_EXIT=0 NS_SHOTS=9024 fast-screen | grep RESULT; done
| Comparison | Conclusion |
|---|
λ_candidate << λ_random (e.g. 8.5 vs 19) | filter is enriching ✓, the theoretical model is usable, proceed to Step 1 |
λ_candidate ≈ λ_random | filter is not enriching ✗ → P(cls=0)≈random → most likely infeasible → realign the GPU filter first, do not start a long hunt |
Only when λ_candidate is clearly below λ_random does the e^(−λ_residual) theory below mean anything; in that case λ_residual = λ_candidate (the measured value, not 8.5).
Step 1: measure P_winner (probability that each candidate is a winner)
Correct method: use empirical data from the actual verify log.
grep "RESULT qubits" /tmp/verify.log > /tmp/all.txt
N=$(wc -l < /tmp/all.txt)
CLS0=$(grep -c "classical=0 " /tmp/all.txt)
PH0=$(grep -c " phase=0 " /tmp/all.txt)
BOTH=$(grep -c "classical=0 phase=0 " /tmp/all.txt)
echo "N=$N cls=0:$CLS0 ph=0:$PH0 both=0(winner):$BOTH"
echo "P(winner) = $BOTH / $N"
Note: the default hunt uses NS_EARLY_EXIT=1, so classical in the verify log is a 0/1 flag (0=clean, 1=at least one mismatch, exited early), not a count. To count the real λ you must use NS_EARLY_EXIT=0 (see Step 0).
If CLS0=0 (no classical-clean observed yet): you do not have P(cls=0), only the upper bound < 1/N. Do not pretend you have a point estimate. Give a conclusion per the "Quick feasibility check" table below (0 out of a few hundred to a few thousand usually = infeasible), and keep accumulating verify runs until ≥1 cls=0 appears before computing. You cannot substitute e^(−λ) (mismatches are correlated, not independent — see below).
If CLS0≥1, use the conditional probability model:
P(winner) = P(cls=0) × P(ph=0 | cls=0)
- P(cls=0) = CLS0 / N (read directly from the data, empirical value)
- P(ph=0 | cls=0): look at the phase distribution among entries with cls≤3, extrapolate the expected μ of phase at cls=0, P(ph=0|cls=0) ≈ e^(-μ)
Example (2026-06-11):
N=6932 cls=0:1 ph=0:3 both=0:0
P(cls=0)=1/6932; cls=0 entry phase=2 → P(ph=0|cls=0)≈e^(-2)≈0.135
P(winner) ≈ 1/51,000 → E[candidates] ≈ 51,000
⚠️ Common mistake: multiplying as if independent
P(winner)=P(cls=0)×P(ph=0) is wrong — cls/ph are positively correlated; you must use the conditional P(ph=0|cls=0).
⚠️ Common mistake: using e^(−λ) as P(cls=0)
Classical mismatches across the 9024 shots are correlated (driven by island structure), not independent Poisson. So P(cls=0) is not equal to e^(−λ_cls). e^(−λ) is only used in "Theoretical prediction" as an extremely rough sanity order-of-magnitude, and only after Step 0 has confirmed the filter enriches. The real P(cls=0) can only be measured empirically (CLS0/N).
⚠️ Common mistake: using estimates from an old circuit
Every change to src/point_add/ (knob/bundle/upstream rebase onto a new frontier) changes λ and the filter alignment; the old P_winner is completely invalid. You must re-measure on the current circuit (including Step 0).
Step 2: measure the candidate generation rate R_cand
tail -1 /tmp/hunt_z3_g1.log
The candidate rate (candidates/M) reflects how tight the filter is; re-measure after any circuit change.
Step 3: measure the verify rate R_verify
wc -l /tmp/verify.log; sleep 60; wc -l /tmp/verify.log
First confirm verify is actually running: grep -c RESULT /tmp/verify.log should ≈ the line count, with no empty nonce | lines (empty lines = verify running dry; under the two-stage pipeline the verify logs are /tmp/lb_s2_g*.log).
Step 4: compute the expected time
E[candidates_needed] = 1 / P_winner (requires the empirical P_winner from Step 1; cannot be computed when CLS0=0, only a lower bound)
R_bottleneck = min(R_cand, R_verify)
E[time_to_win] = E[candidates_needed] / R_bottleneck
Backlog check: if R_cand>R_verify, add backlog_at_win / R_verify.
Theoretical prediction (rough pre-hunt sanity only, never a conclusion)
⚠️ This section has order-of-magnitude meaning only after Step 0 has confirmed the filter enriches. Otherwise λ_residual ≠ 8.5 and the whole section is void.
A stale nonce ≈ a random nonce; its N_cls + N_phase is a rough estimate of λ_raw:
| N_cls + N_phase | Rough difficulty | Recommendation (Step 0/1 confirmation still required) |
|---|
| < 15 | easy | but still measure |
| 15–25 | maybe feasible | must confirm enrichment with Step 0 |
| 25–35 | borderline | most likely needs a single knob |
| > 35 | basically infeasible | switch approach |
The theoretical model (valid only if Step 0 confirms λ_candidate≈λ_residual and << λ_random):
P(winner per candidate) ≈ e^(−λ_residual_cls) × e^(−N_phase). Historically λ_residual≈8-9 when the filter was well aligned, but this is not a constant — the measurement on the new circuit (Step 0) is authoritative.
Quick feasibility check (when you have a small amount of verify data)
| Observation | Conclusion |
|---|
| cls=0 seen ≥1 time and ph=0 seen ≥1 time | feasible, estimate time with the conditional model |
| cls=0 seen 0 times (hundreds to thousands of samples) | P(cls=0) too low → most likely infeasible → check Step 0 for a non-enriching filter |
| Step 0 shows λ_candidate ≈ λ_random | filter not enriching → realign the filter or switch approach, do not grind |
| cls=0 AND ph=0 appears directly | very lucky, P(winner) is high |
⚠️ A wrong way to measure the distribution — do not use it
Wrong: take existing GPU-filtered candidates and run fast-screen under a different circuit config to compare distributions. The GPU filter is specific to a particular circuit; it is meaningless across circuits. Correct: GPU hunt each config separately and collect that config's own candidates before doing statistics.
Steps 0–4 above answer "how long will I wait". The three items below answer the more upstream question "should this path be hunted at all" — cutting off dead ends before burning GPU.
A. Three-channel per-channel-zero hard criterion (the cheapest go/no-go, do it first)
A winner requires cls=0 and phase=0 and anc=0 (all three channels clear). Before running any time estimate, first ask: within this batch of verified candidates, has each of cls, pha, anc independently reached 0 on some candidate?
- If a channel has never reached 0 across a few hundred candidates → it has a structural floor,
0/0/0 is unreachable no matter which nonce you swap in → abandon the path immediately, no need to estimate time.
- If all three channels have each reached 0 (even if never simultaneously) → this screen is passed; proceed to the overlap test / time estimation below.
My existing Step 1 only watches cls and ph; the anc channel must also be independently confirmed to reach 0. anc≠0 usually means a missed uncompute (a structural bug), not something an island can fix.
B. Failing-shot overlap test (distinguish "structural floor" from "statistical long tail" — the single most critical judgment)
Symptom: some channel (usually cls) is stuck at a small floor K across many candidates, never lower (e.g. across a few hundred candidates the best is always 2/*/0, with cls≤1 never seen).
The only question to answer at this point: is K a structural floor (a fixed set of shots fails for every nonce → 0/0/0 unreachable → dead end) or a deep statistical long tail (cls=0 reachable at ~e^−λ, just slow)? Histogram shape (pile-up vs smooth decline) is only a weak signal and untrustworthy with a few hundred candidates. The decisive test:
| Result | Verdict | Action |
|---|
| Failing shots highly overlap across candidates (the same batch of shots repeatedly) | structural floor, a fixed nonce-independent bad set exists | abandon the path; more nonces will not help |
| Failing shots barely overlap across candidates | statistical long tail, an all-clear nonce exists | keep hunting (it is just deep) |
Measured by a peer team: the dead 1210q path SEG182+FOLD17+DIALOGFOLD17 was stuck at cls=2 with a clear pile-up (11 of 392 candidates at cls=2, none lower) → structural floor. Whereas slope1016+compare43 also had best cls=2, but the failing shots of 4 candidates were {2879,6741}/{2689,3336}/{589,7961}/{1062,8584} — zero overlap → statistical long tail, 0/0/0 reachable, just deep.
⚠️ Do not run the bash with zsh: a multi-variable CFG="A=1 B=2" only word-splits into multiple env assignments under bash; under zsh, env $CFG treats it as one invalid variable name and silently builds the base config, so all your island nonces come back dirty — a false all-dirty alarm.
C. A "statistical long tail" can still be a practical dead end (depth kills)
The overlap test ruling "statistical long tail" ≠ landable within your time budget. Estimate the candidate count e^λ requires and compare it to the fleet's actual throughput:
- Peer team measurement of
slope1015+compare43(1203q): 346 candidates, cls floor stuck at 3, zero overlap (genuinely a statistical long tail), but e^9≈8000 candidates are needed per cls=0, and an actual run of 960M nonces produced 0 islands. Overlap says "not structural", but depth kills it anyway.
- Rule: if
e^λ exceeds the candidate budget, abandon the path; do not run it for nothing.
D. apply-aware filter calibration determines the cls floor (an extension of Step 0)
The GPU prefilter is apply-aware: it models the apply-side comparator (e.g. compare_bits=46). A lever that changes the comparator (e.g. compare 46→43) silently throws the filter out of alignment — GPU-CLEAN becomes "clean under the wrong comparator", and the candidates verify stuck at a high cls floor (the earlier compare43 mean≈8-10 was exactly this).
Diagnostic value: when GPU-CLEAN candidates verify far from 0/0/0, first suspect a filter/circuit comparator mismatch before blaming nonce luck. Cost ranking of levers against the filter: pre-GCD changes cost 0 > value-exact apply tweaks cost a little > comparator changes cost the most. When choosing a lever, prefer keeping the filter honest.
E. Three corrections to the quantitative runtime model (refining Step 4)
My Step 4 uses 1/P_winner / R_bottleneck. Three corrections make the absolute value more credible:
- Conditional funnel, not an independent product (I already have cls×ph; add anc and density stratification):
island_rate = d · P(c=0) · P(p=0|c=0) · P(a=0|c=0,p=0)
d = e^(−λ_GCD) # GPU prefilter pass rate, estimated from the [all-nonce] GCD-hard mean (millions of samples, tight)
P(c=0) # residual cls zero rate among GCD-clean candidates (conditional on d)
P(p=0|c=0) # measure directly: fraction of c-clean candidates that are also p-clean (more stable than modeling the pha distribution)
P(a=0|…) ≈ 1 # anc is usually deterministically 0
Key: estimate each rate from a [mean], not by counting rare 0s. Estimate d from the all-nonce GCD-hard mean λ_GCD (huge sample count); do not estimate a ~1e-6 probability by waiting for islands to appear.
- Use Poisson / Negative-Binomial for counts, not Gaussian. cls/pha/anc are non-negative counts of a few failing shots out of 9024, mean μ≈2-6. With dispersion
σ²/μ≈1 use Poisson P(0)=e^−μ; with σ²/μ>~1.2 (GCD-clean is a screened heterogeneous subgroup, usually overdispersed) use NB P(0)=(1+μ/r)^−r, r=μ²/(σ²−μ). With <50-100 candidates the variance is untrustworthy; fall back to Poisson with the mean.
- Calibration constant k + report percentiles. No closed form is accurate to within an order of magnitude (shot-to-shot correlation breaks the independence assumption). Treat the closed form as a relative ranker + ETA prior, and wrap an empirical correction around it:
E[N] ≈ k · (1 / island_rate), k = median(actual_N / predicted_N) over past landed hunts
Every time an island lands, record (predicted, actual) and update k (measured k spreads 0.3×-73× across configs). Waiting times are exponentially distributed, heavy-tailed: percentile P requires ln(1/(1−P))/p nonces, so p99 ≈ 4.6× the mean. Always report p50/p90/p99, never just the mean — "expected 4h" often means "1/100 chance of >18h".
The peer team has a ready-made tool scripts/island_runtime_model.py (density × conditional funnel q × throughput R, automatically classifies screen-bound vs eval-bound). Screen-bound (q≈1, low density) speeds up linearly with more scan GPUs; eval-bound (independent pha/anc pattern, small q) gains nothing from more scan GPUs — you must speed up the verifier or teach the filter to recognize pha/anc triggers. The two-stage pipeline (stage-1 prefilter → stage-2 validate) fits this stratification exactly.
🩸 Lessons (hard-won)
L1 (2026-06-24): the hunt vlog's classical=0 is an early-exit FLAG, not a true cls-clean — nearly mistook a 10-40h hunt for 1-3h
Symptom: the cswap hunt produced "c0 ≈ 29k classical-clean candidates, 0 winners", from which I estimated P(phase=0|cls=0) < 1/29k and "1-3h more to a winner". All wrong.
Root cause: under NS_EARLY_EXIT=1, the classical/phase/ancilla in RESULT are 0/1 FLAGS, not counts. eval runs 64-shot batches in order and breaks at the first bad batch (checking classical first, then phase, then ancilla). Therefore:
classical=0 phase=1 only means "the first bad batch was not classical (phase failed first)"; it in no way means classical is clean across all 9024 shots — in the batches never reached after the break, classical can still fail.- The "c0 fraction ≈ 30%" in the hunt ≈ the fraction where "phase fails before classical", not P(cls=0).
Empirical verification: fully recomputing all 800 candidates the hunt had flagged classical=0 (NS_EARLY_EXIT=0) → cls mean ~7 (range 1-18), 0 true cls=0 (random nonces ~15, so the filter really is enriching, but only down to ~7, not to 0). True cls=0 is a rare ~1/1100 tail.
Consequence: treating the c0 flag as cls-clean ⇒ believing only the phase channel remained ⇒ estimating 1-3h. The truth is a winner needs the joint cls=0 ∧ phase=0 tail (both channels at λ~7) ⇒ P(winner) ~ 1 in hundreds of thousands ⇒ ~10-40h, off by an order of magnitude. The earlier "0/1/0 near-miss" was most likely the same flag illusion too.
Iron rule:
landability / P(winner) may only be judged with full-count cls (NS_EARLY_EXIT=0), never from the early-exit flag.
This is the entire reason Step 0 exists. Lazily reading the hunt's 0/1 flag = tens of hours ground away for nothing.
The hunt runs NS_EARLY_EXIT=1 (saves time, and winner detection is still correct — a true 0/0/0 never breaks), but progress/feasibility judgments require a separate sample fully recomputed.
L2: dd-ON / dd-OFF only changes the cls magnitude; it does not change the pitfall above, nor was it the cause of the misestimate
Same batch of candidates: dd-OFF cls mean ~14, dd-ON ~7 (dd removes dead-CCX → fewer mismatches, correct direction, the .idx adds no false errors). dd-ON is the lower-cls side. So if dd has any effect it only makes the real hunt easier than the proxy; it does not explain "the estimate was too optimistic".
- The displacement in the table / λ is measured dd-OFF (index-shift configs must be dd-OFF, otherwise dd-ON misjudges on a shifted stream, see
hunt-verify-must-be-dd-off). It measures "how many more hard inputs the edit has than base", not the absolute hunt time.
- "λ ≈ base" = "as huntable as base", but base itself is a multi-hour joint-tail hunt for cls=0 ∧ phase=0 (the maintainers pay this cost too). Do not misread "the edit adds no difficulty" as "a winner comes quickly".
