Nemesis: adversarial worlds and rare failures
6,790 words16 subsections11 tables3 listingsPlan version 1.1
On this page16
Crate frob-nemesis, layer 5.
26.1 What Nemesis owns
Randomization from card uncertainty reports the tails it happens to sample. It never looks for a failure and never reduces one to its cause. Nemesis does both. It searches the space of scenes, disturbances and parameters for worlds in which a candidate violates its requirement, keeps only worlds the candidate's own body could have solved, checks that a failure is not an artifact of the simulator, shrinks it to the smallest world that still fails, and stores that world as a regression. It also answers the other question about failures, how rare they are, and keeps the search for failures apart from the bound on their rate.
A value in this chapter that follows from a stated formula is a derived value and a known answer of §26.14; every other number carries its label.
Nemesis owns the legality set, the adversarial search, the solvability oracle, the artifact guard, shrinking and the
format .fmcw, the hard-world set, rare-failure estimation, the audit of screening, and the selection of covering
scene sets. It consumes requirement margins from Arena (§24), scene grammars and typed scene edits from Habitat (§19),
snapshots and forks from Chronicle and Autopsy (§29, §27), promotion between tiers from Kinesis (§16), and through the
airlock FrankenSim's fs-uq, fs-eproc, fs-dfo and fs-archive.
| Mechanism | Tier | Reason for the tier |
|---|---|---|
| Legality set, solvability bookkeeping, artifact guard, hard-world set | S | Bookkeeping over mechanisms that exist elsewhere in the plan |
| Adversarial search by margin | F | Established in falsification practice; its gain over randomization on robots in interiors is unmeasured |
| Minimal counterexample worlds | F | Delta debugging is established for programs; its yield on physical worlds is unmeasured |
| Certification by crude sampling; bounded-weight importance sampling | S | Exact binomial bounds and bounded likelihood ratios |
| Splitting and cross-entropy tilting as exploration | F | Published gains are real and uneven (§26.9) |
| Screening audit; coverage selection | S | Stratified sampling; a greedy algorithm with a classical guarantee |
26.2 Decisions
- ADR-NEMESIS-01. Search inside a legality set, and keep priors apart from admissibility. An unconstrained adversary wins by building worlds no robot is meant to face. Legality is a set; the nominal randomization is a distribution on part of it. A rare but admissible world can be a useful counterexample with negligible operational probability, so the search does not discard it and the report states both facts.
- ADR-NEMESIS-02. Only solvable worlds count. A world is a counterexample to a design only with a witness that the candidate's own body, actuators and mission constraints could have satisfied the requirement in it. This is what separates a useful trap from an impossible one.
- ADR-NEMESIS-03. A failure counts after promotion. A failure found on a fast tier is replayed one tier up and under the numerical variants of §26.6 before it enters any count. FACT (Appendix H): in one study 62.5% of unsafe simulated test cases led to unsafe behaviour on a test track; simulated failures do not all transfer, and the first transfer to check is between our own tiers.
- ADR-NEMESIS-04. Smallest, not worst. The smallest change that flips a verdict is more informative than the world with the lowest score. Every failure is shrunk before it is reported.
- ADR-NEMESIS-05. Exploration and certification never share data. Search-selected, tilted, forked and battery-selected episodes find failures. Only nominal draws, or draws with recorded bounded weights, enter a bound.
- ADR-NEMESIS-06. Everything Nemesis finds is discovery data. Hard worlds and counterexamples train and test designs; they are never a confirmation sample of §24.13.
- ADR-NEMESIS-07. Screens are audited, not trusted. Whatever a cheap stage discards is sampled, and a known winner is planted.
26.3 The search space and the legality set S
A world is a base scene, an edit list, a disturbance schedule and a parameter vector. The base scene is a seeded
derivation in a scene grammar, so it has a SceneId. An edit is one atomic, typed change in authored units. Every
edit declares which causal paths it changes.
| Edit class | Examples | Declares that it changes |
|---|---|---|
| Geometry | A sill height, an edge radius, a door width, the place of an obstacle, a stair riser | Collision geometry and clearance |
| Material | Friction of a floor patch, a compliant mat, the presence of a film | Contact; optics as well if the material is wet or glossy |
| Optics | The position of a light, a glass panel, a reflectance | Sensing only |
| Fixture | A door-closer torque, a conveyor speed, a cart left in an aisle | Dynamics of fixtures |
| Clock and link | A sensor latency, a dropout burst, packet jitter | Timing only |
| Disturbance | A push of stated impulse at a stated time and direction, a payload shift | Exogenous forces |
| Parameter | A value inside a card's uncertainty: actuator gain, friction coefficient, mass, sensor bias | Model parameters |
Moving a light can change the depth-dropout distribution without changing friction, and wetness may change both. An edit that cannot say which path it changes is not admitted, because Autopsy (§27) will later treat the edit as an intervention on one mechanism.
The legality profile. DESIGN: a legality profile, schema frob.legality/1, lists a bound for every editable
quantity with a provenance class: cited with its source, card when it is the uncertainty of a card, or assumed.
Dimensional norms for buildings come from cited sources (OPEN-HAB-1 in §19); until then the bounds are assumed and
every counterexample that touches one says so. Legality is checked on the final world, not only on each edit
(INV-NEMESIS-02): two individually legal obstacles can narrow a passage below its minimum width.
Admissibility and prior. Each world carries its legality verdict with the bounds it touches, and its density under the task's nominal randomization where one is defined. The first decides whether the world may be used; the second says how often it would arise and decides nothing.
Small. The size of a world relative to its base is lexicographic: the number of atomic edits, then the normalized physical distance, each edit's magnitude divided by the width of its legal range.
26.4 The falsification score and the search F
Score. A binary failure has zero gradient almost everywhere. The search therefore minimizes the requirement margin of §24.5, the dimensionless distance of the episode from violating its verdict formula. A world whose margin is negative, after the boundary check of §24.5, is a candidate failure. Minimizing a robustness margin is established falsification practice with a standing tool competition (FACT from a search summary, Appendix H, to be confirmed at the source). The same search serves the design-pair question of §25: for rivals A and B, find a legal world in which the predicted preference reverses by a practically important margin.
Methods. Every campaign runs the first row at equal budget as its baseline arm.
| Method | Space | Foundation | Role |
|---|---|---|---|
| Card-uniform randomization | All | The task's randomization | Baseline arm and fallback |
| Cross-entropy search | Continuous parameters, as normal germs | The proposal fit of fs-uq (FACT: frankensim/crates/fs-uq/src/product_importance/proposal.rs, a weighted mean update at unit covariance) |
Tilts the sampler toward low margin, truncated at legality bounds |
| Derivative-free descent | Continuous parameters | fs-dfo |
Local descent on the margin under common random numbers |
| Quality-diversity archive | Mixed | fs-archive |
Keeps failures binned by failure class and binding atom, so one mode does not absorb the budget |
| Grammar mutation | Discrete edits | Habitat's grammar | Structural changes, guided by which requirement atoms an edit has moved before |
| Splitting on forks | Per-step disturbances | Snapshots and child addresses | Failures driven by noise that arrives after a fork (§26.9) |
A scenario-language sampler given the same generator and the same monitors is an admissible second baseline arm. When
the question is which of two designs is better, the order in which candidate worlds are evaluated may follow a
value-of-information ranking (FACT: frankensim/crates/fs-voi provides a ranking-flip probability); the ranking
orders work and never decides a verdict. Every evaluated world is recorded with its address and with the law that
proposed it, so a later importance-weighted estimate remains possible. Search runs on a fast tier. Nothing it finds is
a counterexample until the oracle and the guard have passed it.
Ceiling, stated before any speed test. HYPOTHESIS: for failures of nominal probability near 3 × 10⁻⁵, the search reaches a first failure with at least 3 times fewer simulated steps than card-uniform randomization (GATE-NEMESIS-02). A planning recomputation that charges the oracle and the shrinking puts the ratio near 6 (Appendix C), and published measurements of adaptive stress testing range from no gain over naive sampling on a policy-in-the-loop task to 2 to 20 times in a driving study (FACT, Appendix H). The ceiling of this lever on the cost of one found failure is therefore under ten, and its effect on the time to a design decision is bounded by the share of that time spent finding failures, which the phase ledger of §39 measures.
26.5 The solvability oracle S
A failing world is classified before it counts.
| Class | Witness | Counts as |
|---|---|---|
solvable-causal |
A controller that uses only the candidate's observation interface satisfies the requirement in this world, within every actuator and mission limit: the baseline controller at other gains, another member of the policy family, or a sampling controller on the candidate's sensors (§22) | A counterexample to the candidate's controller or policy |
plant-feasible |
A trajectory found with privileged state satisfies the requirement within the body's limits | A counterexample, tagged plant-feasible only: the body can do it, and whether the sensors allow it is a separate question for the observation analyses of §20 and §25 |
not-excluded |
Necessary conditions pass (a route exists in the clearance complex of §19, wrench and torque envelopes suffice, the energy budget closes) and no trajectory was found | Unresolved. Reported, not counted either way |
infeasible-for-candidate |
A checked necessary condition fails, with its dual vector or its bottleneck named | Not a counterexample. Counted in Arena's infeasible column (§24.8) and offered to the retrofit query of §19 |
Three rules. A witness is itself a simulated run, so it passes the artifact guard: a witness that succeeds through
solver-created energy is not a witness. An infeasibility verdict needs a checked necessary condition; a failed search
for a witness proves nothing and yields not-excluded. And the oracle runs for the candidate's body, not for a
generic point robot: connectivity of free space at a clearance radius certifies occupancy only, not steering,
traction, reach or perception.
26.6 The artifact guard S
Before a failure or a witness counts, it is replayed three ways (INV-NEMESIS-05).
- One tier up. From the fast tier to
batch-cpuin double precision, and for anything that will enter the hard-world set, on the referee. The decision-level equivalence test of §35 decides whether the higher tier reproduces the failure: the same verdict, the same failure class and the same binding atom, with the failure time inside the recorded envelope. - Numerical variants. Half the step; twice the solver iterations; the alternative contact law; a solver tolerance ten times tighter. These are the perturbations that should not matter to a physical failure (§23).
- Energy audit. The energy ledger of §29 is read for the run. A failure or a witness whose integrator-and-solver residual exceeds its envelope is flagged.
A failure that vanishes under any of these is labelled artifact-candidate with the variant that removed it. It is
excluded from the hard-world set and from counterexample counts, and it is written to the fidelity ledger of §16 as a
tier-sensitive case, because a failure of the simulator is also a finding. Two planted artifacts seed the negative
controls: a friction cone linearized as a box grants √2 times the friction coefficient along its diagonals, and
penetration recovery can pump energy into a hopping body.
26.7 Shrinking to a minimal counterexample world F
Input. A failing world w = base ⊕ {e₁ … e_n} whose base passes. If the candidate fails in the base world there is nothing to shrink and the base is the counterexample.
Test relation. A subset of the edits fails when the world built from it is legal, replays the candidate deterministically, violates the same requirement atom with the same failure class, and does so on at least 48 of 64 paired seeds (TARGET). A subset that fails by a different mechanism is not a pass and not the same failure: it is recorded as a separate finding with its own classification, and the shrink continues on the original mechanism.
Algorithm. Delta debugging. Partition the edits into k parts, starting at k = 2. If some part fails, recurse on it. Otherwise if some complement fails, recurse on it with k − 1 parts. Otherwise double k, and stop when k exceeds the number of edits. The result is 1-minimal: removing any single edit makes the failure disappear. Then each remaining continuous edit is moved toward its nominal value by bisection until the failure is lost, and the last failing value is kept.
What minimal means. 1-minimal under removal of atomic edits, and nothing stronger. Counterexample: let the world fail when edits a and b are both present or when c, d and e are all present. With the edits listed as (a, c, d, e, b), delta debugging tests the halves {a, c} and {d, e, b}, which pass, then the singletons and {e, b}, which pass, then finds that the complement {c, d, e, b} fails, and ends at {c, d, e}: three edits, 1-minimal, while the two-edit counterexample {a, b} exists. DESIGN: when the original list has at most 12 edits, every subset of one or two edits is also tested, 78 tests at most, and the smaller counterexample replaces the result. A world that passes this check is labelled minimum among pairs; no world is called the closest failure, because failure sets are not monotone.
Size. TARGET: at most three atomic edits. A shrunk world with more is kept and labelled non-minimal(k).
The file. Format FMT-FMCW, extension .fmcw, schema frob.mcw/1.
{ "schema": "frob.mcw/1", "id": "w:3fa9…", "task": "t:kitchen-tray@88c1…", "requirement": "delivered",
"candidate": {"model": "m:9f2c…", "controller": "c:5e02…", "policy": "p:11d0…"},
"base": {"scene": "s:kitchen-17@a4e0…", "world": {"run_seed": 901, "world": 5120, "episode": 3}},
"edits": [
{"op": "set", "path": "/floor/patch[galley-2]/film", "from": "dry", "to": "grease", "changes": ["material"]},
{"op": "set", "path": "/fixtures/door[pass]/closer_torque", "from": "14 N·m", "to": "21 N·m",
"changes": ["fixture"]} ],
"minimality": {"kind": "1-minimal", "pairs_exhausted": true, "tests": 37, "seeds_failing": "61/64"},
"failure": {"class": "slip", "binding_atom": "upright", "margin": -0.42, "time_s": "11.3"},
"replay": {"backend": "gpu-cuda", "class": "D2", "state_digests": "b3:0c55…"},
"promotion": {"tier": "referee", "reproduced": true,
"variants": ["half-step", "iterations-x2", "law-2", "tol-div-10"]},
"oracle": {"class": "solvable-causal", "controller": "c:77e1…", "margin": 0.18, "trace": "b3:a9d2…"},
"legality": {"inside": true, "touched": [{"bound": "closer_torque", "provenance": "assumed"}]},
"prior": {"log10_density_ratio": -3.9},
"neighbours_passing": ["w:51b0…", "w:e7c4…"],
"evidence": {"class": "Tested", "tier": "referee", "standing": "established"},
"authorization": {"execution_authorized": false, "hardware_safety_signoff": false,
"sim_to_real_certified": false} }
The file carries what replays it (INV-NEMESIS-04): identities, edits, addresses and state digests. A file that does not replay with identical digests on its originating backend is invalid. It also carries its passing neighbours, the worlds with one edit removed. By 1-minimality they exist, and each is an interventional contrast in the sense of §27: the failing world and its neighbours are the two experiments that are carried through the loop together, the failure and the edit that removes it. A minimal world is also the input to the retrofit question of §19, whether a cheap amendment to the place fixes the failure with the policy frozen.
The loop. Propose a design; search for violating worlds; classify; guard; shrink; update the hard-world set and the region of worlds the design is known to handle; edit the design or the place; repeat.
26.8 The hard-world set S
For each task family and robot class, Nemesis keeps a versioned set of minimal counterexample worlds, schema
frob.hardset/1, as a list of .fmcw identities with the failure mode each exposes. nemesis.hardset run evaluates
a design against the set of its class and returns a scorecard with the columns of §24.8. A world enters the set only
as solvable-causal or plant-feasible and only after promotion on the referee. A world leaves the set by a recorded
decision. Three uses are refused: as a confirmation sample (FROB-REF-567), as nominal draws for a bound
(FROB-REF-560), and as the only content of a battery, since a battery made of past failures overfits them (§26.11).
26.9 Rare failures: exploration and certification
Two questions are routinely confused. Where does this design fail? is a search, and any method that finds failures
faster is welcome. Is its failure probability below p⋆? is a claim, and only estimators with a valid finite-sample
bound may make it. The certification lane issues a statistical bound; its proof class is Tested at confidence 1 − δ,
never Certified, which §12 reserves for certificates a checker accepted.
| Estimator | Returns | Valid bound at a fixed budget | Lane | Foundation |
|---|---|---|---|---|
| Crude nominal sampling, zero-failure rule | p ≤ 1 − δ^(1/n) after n episodes without a failure | Yes, exact | Certification | Ours; integer counts and outward rounding |
| Crude nominal sampling, sequential | A confidence sequence for p that ends certified, refuted or exhausted | Yes, at any stopping time | Certification | fs-eproc (FACT: frankensim/crates/fs-eproc/src/bernoulli.rs, a Beta(½, ½) mixture with a cap of 10⁶ samples) |
| Bounded-weight importance sampling | An estimate of p, a two-sided confidence sequence, and a lower bound for refutation | Yes, for an explicit Gaussian law and a proposal fixed before the run | Certification, for refutation and for estimates | fs-uq (FACT: frankensim/crates/fs-uq/src/product_importance.rs) |
| Cross-entropy tilting | A proposal for a later stage; failures | No | Exploration | fs-uq proposal fit |
| Splitting on forks | Failures; a rate that is unbiased in theory | No | Exploration | Ours, on Chronicle's forks |
| Extreme-value extrapolation | Not built | Checking a fitted tail at 10⁻⁶ takes the same nominal episodes that certify directly | — | — |
Crude sampling S. The cost of a claim is fixed by arithmetic. With δ = 0.05:
| Target p⋆ | Nominal episodes with no failure | Time at an illustrative 400 episodes per second |
|---|---|---|
| 10⁻⁴ | 29,956 | 75 s |
| 10⁻⁵ | 299,572 | 12.5 min |
| 10⁻⁶ | 2,995,731 | 2.1 h |
Throughput is §36's to establish; the middle column does not move. Inside the qualification lane the level is that of the request, so the tenth request needs 76,959 clean episodes for 10⁻⁴ instead of 29,956 (§24.13). Proving absence has a fixed price that no sampler discounts without assuming where the failures live.
Bounded-weight importance sampling S. The proposal is a defensive mixture q = ε·p + (1 − ε)·p_shifted, so the
likelihood ratio w = p/q is at most 1/ε, and ε·w·1[failure] is an observation in [0, 1] whose mean is ε·p. A
confidence sequence on that mean, divided by ε, bounds p at every stopping time. What fs-uq provides (FACT, same
file): exactly this construction for parameters that are independent or jointly Gaussian in normal germs, a proposal
chosen before the run or fitted on a separate completed pilot whose data are never reused, checkpoints, and a cap of
10⁶ evaluations. What we add (DESIGN): declared monotone transforms from normal germs to non-Gaussian card
distributions on our side of the airlock; the same mixture for discrete scene edits, where the weight bound holds for
the same reason; and a variance-adaptive betting sequence on the scaled observation, because the range-based sequence
that fs-uq feeds is, in its own words, much wider than the descriptive error for rare events. The scope is narrow
and is stated in every result. With weights bounded by 1/ε, the upper bound after n runs without a failure cannot fall
below about ln(1/δ)/(ε·n), so importance sampling is never the cheaper way to certify absence. It earns its place in
two cases: refuting a target, by a lower confidence bound that exceeds p⋆, and tightening an estimate once failures
have been observed.
Exploration F. Cross-entropy tilting moves static parameters toward low margin; it needs whole episodes and reuses no snapshot. Splitting restores a snapshot of a world that has reached a distress level and continues it many times under fresh per-step disturbances. DESIGN: a child world has the address of its parent extended by a fork path, its per-step disturbance streams after the fork tick are re-keyed by the child address (the replicate mode of §27.3), and its prefix is shared bit for bit. The distress score is an online past-time margin (§24.5) with fixed levels chosen before the run. A fork replays its parent identically unless noise enters after the fork, so splitting applies only to failures driven by per-step disturbances; a request to split on static parameters alone is refused (FROB-REF-569).
TARGET, in its surviving form: with an informative score, exploration reaches failures of nominal probability 10⁻⁴
to 10⁻⁵ with 10 to 100 times fewer episodes than crude sampling. FACT (Appendix H): the measured gains in the sources
read are 2 to 20 times in one driving study and about 5 times in mean-square error on one policy-in-the-loop task.
Splitting needs per-step disturbances; tilting and the defensive mixture also act on static scene parameters. The
evidence cuts both ways (FACT, Appendix H). The splitting estimator is unbiased whatever the score and the number of
replicas. In one published study adaptive splitting with temporal-logic scores estimated 3.5 × 10⁻⁴ for a true
4.8 × 10⁻⁵, with a spread five times the mean, and its authors note that neither splitting nor sampling has a
guarantee on estimation error at a fixed budget; in the same study a cross-entropy sampler returned 7.6 × 10⁻²² for a
true 2.0 × 10⁻³. On a policy-in-the-loop task at p near 2.5 × 10⁻⁵, plain splitting had a relative mean-square error
of 1.02 against 1.09 for naive sampling. That is why exploration issues failures and rates labelled Estimated, and
never a bound.
The catalogue of modes. Every failure that passes the guard is filed by failure class and binding atom. A Good–Turing monitor estimates the probability mass of modes not yet seen as the number of modes seen exactly once divided by the number of failures seen. It is the stopping signal for exploration.
The decision model. States: the finalist's failure probability is below the target p⋆ or not. Actions: explore, draw nominal episodes, stop and certify, stop and refute, stop exhausted. Loss: a false certification costs far more than a false refutation, which costs more than wasted episodes. The policy is a fixed table, not an adaptive controller.
Decision: Is the failure probability of finalist F on task T, at tier X, below p⋆?
Policy: 1. Explore to 20% of the budget, or until the unseen-mode mass is at most 0.05.
2. If a bounded-weight or nominal lower bound exceeds p⋆: stop, refuted.
3. Spend the rest on nominal episodes under the sequential binomial bound.
4. End certified (upper bound below p⋆), refuted, or exhausted with the bound reached.
Applies to: Finalists only. A screening rung never buys a rare-failure bound.
Obligation: The bound holds at confidence 1 - delta for independent nominal episodes with a failure
predicate frozen before sampling, scoped to its tier and its randomization.
Primary risk: Exploration data leaking into the bound. Countermeasure: episodes carry their proposal
law; the bound refuses any episode not drawn nominally (INV-NEMESIS-03).
Failure modes: An uninformative distress score; forks that carry no fresh randomness.
Fallback: Crude nominal sampling alone.
Fallback trigger: Under 1% of forks reach the next level; a failed null self-test of the bound.
Budgeted mode: Exploration at most 20% of the budget; then a refusal that carries the bound reached.
Baseline: Crude nominal sampling with the zero-failure rule at the same budget.
Rollback: A configuration flag to the baseline; bounds already issued stay valid.
Verification: Coverage of the bound on synthetic studies with known p; planted two-mode failure found;
a tilted episode offered to the bound is refused. Shadow first, then default.
Worked numbers, illustrative. Splitting to 10⁻⁶ with six levels of conditional probability 0.1 and 10⁴ continuations
per level uses 6 × 10⁴ fragments, about fifty times fewer than the 3 × 10⁶ nominal episodes of the table, and under
independence its coefficient of variation is at least √(6 × 0.9 / (0.1 × 10⁴)) = 7%; correlation between continuations
of one parent makes it larger. If throughput is ten times lower than illustrated, the 10⁻⁶ claim costs 21 hours:
certify 10⁻⁵ and report 10⁻⁶ as Estimated.
Scope of every bound. The probability is under the task's nominal randomization, on the stated tier, for the frozen requirement. It is a statement about the model at that tier. Under the claims of §8 it is never Reality, and a bound obtained on a fast tier is provisional until promoted.
26.10 Auditing what screening discarded S
The cascade of §28 spends cheap stages to discard designs before expensive ones. A comparison among survivors says
nothing about what was discarded: an e-value between the eighth and ninth finalists is silent about the design a
screen threw away at the first rung. Nemesis audits every screening stage in two ways. This section owns the
audit: its verb is nemesis.audit, its gate is GATE-NEMESIS-07, and the cascade applies it stage by stage without
restating it (§28.12).
- Sampling discarded strata. Discards are stratified by reason for discard, design family and score band. Before any score exists, a keyed random draw assigns a share of each stratum to the audit lane, 10% of the stage's spend (TARGET). Audited designs run at the next stage at a fixed sample size as if they had survived, and are never cancelled by a race. The result is a false-discard rate per stratum with an exact binomial bound: with no top-k design among m audited discards the rate is at most 1 − δ^(1/m), which is 9.5% at m = 30 and 5.0% at m = 59 for δ = 0.05. The approximation ln(1/δ)/m (10.0% at m = 30) is not used.
- Planting a winner. A design whose rank at the final stage is known from an earlier full evaluation, and which the screen represents poorly, such as a gait outside the atlas or a body far from the policy family's training set, enters the population under a blinded identity. It must survive every screen.
A missed planted winner, or an audited miss rate above the declared tolerance, labels the campaign's results
screen-biased and bypasses the stage for the affected strata until it is re-qualified. The audit lane is also the
only calibration source for the rank-agreement measurement between rungs (§28): it supplies designs that were not
selected by the scores being calibrated.
26.11 Covering scene sets by submodular selection S
A battery has a budget, and the scenes worth running are those that expose failure modes other scenes miss. DESIGN:
- Incidence. A matrix of scenes against failure modes, built from the catalogue of §26.9 over a reference set of designs. A scene exposes a mode when at least one reference design fails in that mode in that scene after the guard. Each mode has a declared weight: frequency × severity × number of designs affected.
- Objective. f(S) is the total weight of modes exposed by at least one scene of S. It is monotone and submodular: a scene is worth only what earlier scenes missed.
- Algorithm. Lazy greedy selection: keep scenes in a priority queue by their last computed marginal gain, and recompute only the top, since gains never increase.
- Certificate. For a selection S of k scenes, the best selection of k satisfies OPT_k ≤ f(S) + the sum of the k largest remaining marginal gains (PO-NEMESIS-03). Greedy also guarantees f(S) ≥ (1 − 1/e)·OPT_k at fixed cardinality. With unequal scene costs the selection ranks by gain per second and the guarantee weakens to the constant of the cost-benefit variant; the certificate still applies and is usually far tighter than either constant.
- Held-out slots. One slot in five is filled at random from held-out scenes, so the battery cannot consist only of yesterday's failures.
Worked instance, illustrative: 40 modes of total weight 100. Greedy gains of 31, 22, 14, 9, 6 and 4 cover 86. The six largest remaining gains sum to 12, so OPT₆ ≤ 98 and the selection is within 88% of the best six-scene battery, against a worst-case guarantee of 63%.
Decision: Which k scenes form the covering battery for robot class C?
Loss: Uncovered mode weight against battery runtime.
Obligation: Weighted coverage is monotone submodular; the certificate above is checked on every
selection and stored with the battery.
Failure modes: The battery overfits past failures; the taxonomy changes under it.
Fallback: The standard battery of §38.
Fallback trigger: Any identity change (model class, tier, kernel versions, taxonomy) since the incidence
was built.
Budgeted mode: Any greedy prefix is a valid battery with its own certificate.
Interference: A rare-failure bound refuses battery-selected episodes (§26.9).
Verification: Lazy greedy equals plain greedy; brute-force optimum on instances of 20 scenes or fewer
lies under the certificate; the worked instance.
26.12 Verbs and refusals
| Verb | Kind | First milestone | Notes |
|---|---|---|---|
nemesis.search |
run | M3 | Candidate, task, legality profile, method, budget. Returns classified candidate failures and the baseline arm's count at equal budget |
nemesis.oracle |
run | M3 | Classifies one world for one candidate and returns the witness or the failed necessary condition |
nemesis.shrink |
run | M3 | Shrinks a promoted failure and writes a .fmcw |
nemesis.bound |
run | M3 | Modes certify, refute and estimate for a failure probability against a target, with the decision model of §26.9 |
nemesis.audit |
run | M4 | Audits a screening stage: stratified discards and a planted winner |
nemesis.cover |
read | M3 | Selects a covering scene set and returns it with its certificate |
nemesis.hardset |
read, run | M3 | show, add, retire and run on the hard-world set of a class |
| Code | Refusal |
|---|---|
| FROB-REF-360 | A world or edit lies outside the legality profile; the violated bound is named |
| FROB-REF-361 | The request demands cited bounds and the profile has an assumed bound on a touched quantity |
| FROB-REF-362 | An edit does not declare the causal paths it changes |
| FROB-REF-560 | A bound was offered episodes that were not drawn nominally or with recorded bounded weights |
| FROB-REF-568 | The failure predicate changed after sampling began |
| FROB-REF-569 | Splitting requested where no randomness enters after the fork |
| FROB-REF-563 | Importance sampling outside its admitted law, or with a proposal fitted on the run it is applied to |
| FROB-REF-564 | Shrinking requested for a failure that does not replay, or that the guard labelled an artifact candidate |
| FROB-REF-565 | Coverage selection on a stale incidence |
| FROB-REF-566 | A planted winner's rank is not on record from a full evaluation |
| FROB-REF-567 | A hard-world or search-selected world offered as a confirmation sample |
| FROB-REF-760 | The episodes a claim needs at its level exceed the budget; the bound reachable within budget is attached |
26.13 Invariants and proof obligations
- INV-NEMESIS-01. Only solvable worlds count: no world without a
solvable-causalorplant-feasiblewitness enters the hard-world set or a counterexample count. - INV-NEMESIS-02. Every world Nemesis evaluates is inside the legality profile, checked on the final world.
- INV-NEMESIS-03. Exploration data never enter a certification bound.
- INV-NEMESIS-04. A
.fmcwreplays with identical digests on its originating backend. - INV-NEMESIS-05. A failure and its witness count only after the artifact guard.
- INV-NEMESIS-06. Hard-world and search-selected worlds are discovery data.
| Obligation | Statement | Class sought |
|---|---|---|
| PO-NEMESIS-01 | The shrinker's output is 1-minimal under its test relation | Tested: property test on random monotone and non-monotone predicates |
| PO-NEMESIS-02 | Under a defensive mixture with nominal share ε every weight is at most 1/ε, and the weighted estimator is unbiased under the admitted law | Tested against closed-form tails; the weight bound is a one-line inequality on file |
| PO-NEMESIS-03 | OPT_k ≤ f(S) + the k largest remaining marginal gains, for monotone submodular f | Tested by brute force on small instances; the argument is on file in docs/derivations/ |
| PO-NEMESIS-04 | n ≥ ln(1/δ)/p⋆ clean nominal episodes give P(no failure in n) < δ whenever p > p⋆, since (1 − p)ⁿ ≤ exp(−p·n) | A candidate theorem card for §12; Tested by exact binomial arithmetic until a checker accepts it |
26.14 Known answers
| Known answer | Expected | Negative control |
|---|---|---|
| Planted illegal edit | Refused with FROB-REF-360 and the bound named | A profile with the bound removed admits it |
| Planted impossible trap: a doorway narrower than the body | infeasible-for-candidate with the bottleneck; never a counterexample |
An oracle that checks a point robot calls it solvable |
| Planted solvable trap of known nominal probability | Found; a causal witness attached | Card-uniform randomization at the same budget, as the baseline |
| Planted artifacts: box-cone traction; energy-pumping penetration recovery | artifact-candidate, with the variant that removed each |
A genuine planted failure survives every variant |
| Shrinking planted causes of size 1, 2 and 3 among 8 to 32 edits | The planted set exactly | The order-dependence example: {c, d, e} before the pair check, {a, b} after |
| Zero-failure rule | 29,956, 299,572 and 2,995,731 episodes at δ = 0.05 | An episode count from ln(1/δ)/p⋆ rounded down |
| Gaussian tail by defensive mixture | P(z > 4) = 3.167 × 10⁻⁵ recovered inside the confidence sequence with shift 4 and ε = 0.1; every weight at most 10 | A mixture without its nominal share on a mis-centred proposal |
| Splitting on a biased random walk | The probability of reaching level 20 before level 0 from level 1, with up-probability 0.4, is 0.5/(1.5²⁰ − 1) = 1.504 × 10⁻⁴ | A walk with no noise after the fork returns identical children and is refused |
| Good–Turing monitor | Unseen mass on a synthetic catalogue with known mode probabilities, inside its interval | A monitor that counts distinct modes instead of modes seen once |
| Coverage certificate | The worked instance: 86 covered, OPT₆ at most 98 | A selection that double-counts a mode |
| Screening audit | A planted winner removed by a deliberately biased screen is reported | A screen with no bias passes |
26.15 Gates, kill gates and pilots
| Gate | Claim | Threshold (TARGET) | Earliest |
|---|---|---|---|
| GATE-NEMESIS-01 | Known answer | Legality and oracle: 100 of 100 planted illegal edits refused; 0 of 100 planted impossible traps counted; at least 95 of 100 planted solvable traps receive a witness | M3 |
| GATE-NEMESIS-02 | Design comparison | On planted traps of nominal probability at most 3 × 10⁻⁵, in 30 paired repetitions, the search reaches a first promoted failure with at least 3 times fewer simulated steps than card-uniform randomization at a 95% lower bound, and at least 70% of reported counterexamples are solvable-causal or plant-feasible |
M3 |
| GATE-NEMESIS-03 | Known answer | Shrinking: planted causes recovered exactly in at least 95 of 100 trials; every .fmcw replays with identical digests in 100 of 100; on unplanted failures the share of worlds with at most three edits is recorded |
M3 |
| GATE-NEMESIS-04 | Known answer | Bounds: over 10⁴ synthetic studies with known p the 95% upper bound covers p in at least 95%; the defensive mixture covers under a mis-centred proposal; non-nominal episodes are refused | M3 |
| GATE-NEMESIS-05 | Design comparison | Exploration: on planted failures of probability 10⁻⁴ and 10⁻⁵, one with two separate modes, at equal episode budget and 30 repetitions, exploration reaches failures with at least 10 times fewer episodes than crude sampling at 10⁻⁵, and both modes are found in at least 80% of repetitions | M3 |
| GATE-NEMESIS-06 | Known answer | Guard: 100 of 100 planted artifact failures labelled and none in the hard-world set; at least 95 of 100 genuine planted failures survive promotion | M3 |
| GATE-NEMESIS-07 | Known answer | Screening audit: a planted winner removed by a biased screen is reported in 100 of 100 runs; the stratified bound covers the planted false-discard rate in at least 95% of 1,000 synthetic campaigns | M4 |
| GATE-NEMESIS-08 | Known answer | Coverage: lazy and plain greedy agree; on 1,000 random instances of at most 20 scenes the brute-force optimum is at or below the certificate and greedy is at or above (1 − 1/e) of it | M3 |
| ✖ KILL-NEMESIS | — | Trigger: GATE-NEMESIS-02 fails after one repair cycle. Fallback: the search methods are removed; Nemesis keeps the legality profile, the oracle, the guard and shrinking, applied to failures that card randomization finds | M3 |
| ✖ KILL-RARE | — | Trigger: in the exploration pilot the gain is below 10 times at 10⁻⁵, or the coverage of any interval offered as a bound is below 85%, or a planted mode is missed in more than 20% of repetitions. Fallback: crude nominal sampling with the binomial bound alone; splitting is removed and tilting is kept only inside nemesis.search |
M3 |
| ✖ KILL-MCW | — | Trigger: on unplanted failures fewer than half of shrunk worlds have at most three edits, or fewer than 90% replay. Fallback: Nemesis ships full failing worlds with replay and the single-edit contrasts ranked by margin; the format stays | M3 |
Pilots before funding. Both Frontier claims have a paper-scale pilot that runs before their work packages are funded. For exploration: planted failures of known probability 10⁻⁴ and 10⁻⁵ on one quadruped, one of them with two separate failure modes; crude sampling, splitting, subset simulation and the defensive mixture at equal episode budget, 30 repetitions; the falsifier is the trigger of KILL-RARE. It needs tens of CPU core-hours on the CPU referee, or on a development oracle outside the product (§38) if it runs before M1. Its ceiling is stated in advance: a clean bound at 10⁻⁵ costs about 3 × 10⁵ episodes whatever the explorer does, on the order of one or two training runs, so a perfect explorer saves at most about a factor of three on a finalist and nothing on other candidates. For search and shrinking: ten planted traps in two generated interiors on the CPU referee, the search against card randomization, with the falsifier of GATE-NEMESIS-02.
26.16 Open questions
- OPEN-NEMESIS-1. Sources for the legality bounds of interiors. Owner: project lead, with OPEN-HAB-1. Blocks
claims that a counterexample is realistic, not its validity. Default: bounds are
assumedand counterexamples say so. - OPEN-NEMESIS-2. The distress score when the requirement margin is flat until shortly before failure. Owner: Nemesis lead. Blocks GATE-NEMESIS-05. Default: no splitting for that requirement; crude sampling.
- OPEN-NEMESIS-3. The compute envelope for a 10⁻⁶ claim, which exceeds the one-hour job rule of §21 at the
illustrated throughput. Owner: project lead. Default: certify to 10⁻⁵ and report 10⁻⁶ as
Estimated. - OPEN-NEMESIS-4. The sample caps of 10⁶ in
fs-eproc's Bernoulli sequence and infs-uq's importance execution, and the absence of splitting upstream. Owner: airlock maintainer. Default: our own exact binomial bound for larger counts; upstream work items FD-FSIM-18 and FD-FSIM-19 are open (Appendix F) and no milestone waits on them. - OPEN-NEMESIS-5. How a hard-world set is carried across a change of robot class or task version. Owner: Arena lead. Default: a set belongs to one class and task version; worlds are re-promoted before they enter another.