DEST v0.9 — Breakdown Lattice

From Weighted Cascade Coverage to Mixed Release, Correlated Beliefs, Deadlines, and Dynamic Feasibility

Version: v0.1
Date: 2026-08-14
Parent: DEST v0.8 Fixed-Cost Certificate Cascade Model
Document type: theorem/counterexample classification paper + executable small-model census

Abstract

DEST v0.8 isolated a genuine theorem region inside the research Runtime:

F_{\mathrm{cov}}(S) = \sum_{v\in\cup_{i\in S}A_i}w_v, \qquad w_v\ge0,

is normalized, monotone, and submodular whenever each inspection has a fixed deterministic affected set $A_i$ .

The present paper asks what happens when the Runtime mechanisms removed by v0.8 are restored one at a time.

The answer is not one linear "submodularity disappears" story.

Different mechanisms break different mathematical assumptions:

valid-release utility can destroy monotonicity while preserving submodularity under a one-blocker condition;
multiple blockers can destroy submodularity in a three-node deterministic model;
correlated belief updates can destroy adaptive submodularity with only two stochastic items, even when the realized utility is pointwise modular;
deadlines make value depend on clock/order, so a static set function is generally the wrong object;
dynamic costs need not alter utility submodularity at all, but they destroy the fixed feasible family of a static knapsack problem.

Therefore the correct object is not a one-dimensional ladder but a Breakdown Lattice separating:

utility structure;
stochastic observation structure;
sequence/time structure;
feasibility/cost structure.

The paper introduces a four-state property language:

\boxed{ \{\mathrm{TRUE},\mathrm{FALSE},\mathrm{CONDITIONAL},\mathrm{NOT\ APPLICABLE}\} }

to avoid confusing a genuine counterexample with a type change.

1. Property language

For every model class we track:

static_set_function;
normalized;
monotone;
submodular;
adaptive_model_required;
adaptive_submodular_general;
order_time_invariant;
static_feasible_family.

A property may be:

\mathrm{TRUE}

or:

\mathrm{FALSE}.

But two additional states are required.

CONDITIONAL

The property may hold only under additional assumptions.

NOT_APPLICABLE

The model is no longer the mathematical object to which the property directly applies.

Example:

An order-sensitive deadline scheduler is not automatically a "non-submodular set function"; it may simply no longer be a set function at all.

1.1 Terminology guardrail: "Breakdown Lattice"

Breakdown Lattice is the engineering name of this classification program.

The canonical formal object established in v0.9 is currently:

\boxed{ \text{a typed regime DAG plus a property-label map}. }

This paper does not claim that the eight named regimes themselves form a lattice in the strict order-theoretic sense. In particular, closure under meet and join has not been established for the named regime family.

If a later version defines a mechanism-configuration poset and proves the required meet/join structure, the word "lattice" may be promoted from project name to mathematical theorem.

2. The Breakdown Lattice

The main utility branch is:

PURE CASCADE COVERAGE
        |
        + release value
        |
        +-- blocker count <= 1
        |      → submodular
        |      → may be non-monotone
        |
        +-- blocker count >= 2
               → no universal submodularity guarantee

The stochastic branch is:

fixed outcome
   |
   + uncertain outcome
   |
   +-- independent modular outcomes
   |      → adaptive modular special case
   |
   +-- correlated outcomes
          → adaptive-submodularity can fail

The time/feasibility branch is:

fixed utility + fixed cost
        |
        + deadline/time value
        |      → order/time-dependent objective
        |
        + dynamic cost
               → changing feasible family

The full Runtime combines all three branches.

3. Layer L0 — Pure Cascade Coverage

From v0.8:

F_{\mathrm{cov}}(S) = \sum_{v\in\cup_{i\in S}A_i}w_v.

With:

w_v\ge0

and fixed $A_i$ ,

\boxed{ F_{\mathrm{cov}} \text{ is normalized, monotone, and submodular}. }

This is the theorem region.

4. Layer L1 — Add Valid Release

For valid quarantined node (u),

h_u(S) = r_u \mathbf1[u\in S] \mathbf1[S\cap B_u=\varnothing].

If:

|B_u|\le1

for every positive-release valid node, v0.8 proved the mixed utility remains submodular.

But a 2-node model already destroys monotonicity:

a invalid → u valid

with:

r_u=1,\qquad w_a=0.1.

Thus:

F(\{u\})=1 > 0.1 = F(\{a,u\}).

So Layer L1 is:

\boxed{ \text{submodular but not generally monotone}. }

5. Layer L2 — Multiple Blockers

A positive-release valid node with:

|B_u|\ge2

admits a universal-weight counterexample.

The minimum deterministic witness has three nodes:

0 invalid → 1 invalid → 2 valid release

For:

S=\{2\}, \qquad T=\{0,2\}, \qquad e=1,

v0.8 obtained:

\Delta(e\mid S)=-0.9 < 0 = \Delta(e\mid T).

Therefore:

\boxed{ \text{multiple blockers are the first deterministic submodularity-break region}. }

6. Layer L3 — Belief Update Requires a New Object

Suppose item outcomes are unknown.

A policy observes selected outcomes and updates beliefs about unselected items.

The relevant object is now a realization-dependent utility:

f(S,\phi)

and a partial realization:

\psi.

For an unobserved action (e), adaptive marginal utility is:

\Delta(e\mid\psi) = \mathbb E[ f(\operatorname{dom}\psi\cup\{e\},\Phi) - f(\operatorname{dom}\psi,\Phi) \mid \Phi\sim\psi ].

Adaptive submodularity requires:

\psi\subseteq\psi' \quad\Longrightarrow\quad \Delta(e\mid\psi) \ge \Delta(e\mid\psi').

7. Theorem 9 — Independent Modular Outcomes Form an Adaptive-Modular Special Case

Let each binary item (e) have outcome:

\Phi(e)\in\{0,1\}.

Define realized utility:

f(S,\phi) = \sum_{e\in S}v_e\phi(e), \qquad v_e\ge0.

Assume item outcomes are mutually independent.

For unobserved (e),

\Delta(e\mid\psi) = v_e P(\Phi(e)=1\mid\psi).

By independence:

P(\Phi(e)=1\mid\psi) = P(\Phi(e)=1).

Hence:

\boxed{ \Delta(e\mid\psi) = v_eP(\Phi(e)=1) }

for every compatible partial realization not already observing (e).

So the adaptive marginal is constant.

Therefore this model is an adaptive modular special case and hence adaptive submodular. $\square$

8. Proposition 10 — Correlation Alone Can Break Adaptive Submodularity

Two binary items (A,B).

Let:

P(A=0,B=0)=\frac12,

P(A=1,B=1)=\frac12.

All other outcomes have probability zero.

Use pointwise modular utility:

f(S,\phi) = \sum_{e\in S}\phi(e).

Before any observation:

\Delta(B\mid\varnothing) = P(B=1) = \frac12.

After observing:

A=1,

perfect correlation gives:

P(B=1\mid A=1)=1.

Thus:

\Delta(B\mid A=1)=1.

Therefore:

\boxed{ \frac12<1 }

and adaptive diminishing returns fails.

So:

\boxed{ \text{pointwise modularity does not imply adaptive submodularity under correlated priors}. }

The minimum action count is two.

9. Exact Binary Prior Census

The executable census enumerates all rational two-item joint distributions with denominator:

D\le8.

The first violation already exists at:

\boxed{D=2}.

That witness is exactly:

P(00)=1/2
P(11)=1/2

The same program separately checks a grid of independent product distributions and confirms that the modular adaptive marginal remains invariant under observing the other item.

The proof, not the grid, establishes the independent special case.

10. Layer L4 — Deadlines

Deadlines produce a different type of breakdown.

Consider two unit-time inspections:

A: deadline 1, reward 1
B: deadline 2, reward 1

Selecting the same set:

[ {A,B} ]

in order:

A\to B

gives value:

[ 2. ]

But order:

B\to A

gives value:

[ 1. ]

Thus:

\boxed{ \text{same selected set} \neq \text{same utility}. }

There is no static set function:

[ F({A,B}) ]

that represents both schedules.

Therefore the right classification is not simply:

submodular = false.

It is:

\boxed{ \text{static_set_function = FALSE} }

and:

\boxed{ \text{submodular = NOT_APPLICABLE} }

for the full order-sensitive objective.

At a fixed time slice, a residual coverage component may remain submodular; the schedule-level problem has changed type.

11. Minimal Deadline Breaks

A single action is enough to show time dependence.

If:

V(\{e\},t_0)=1

but:

V(\{e\},t_1)=0,

one static set-function value:

[ F({e}) ]

cannot equal both.

Two actions are the minimum needed to exhibit order dependence while holding the selected set fixed.

12. Layer L5 — Dynamic Cost

Dynamic cost is yet another orthogonal breakdown.

Let budget:

B=1.

One inspection (e) has:

c_e(t_0)=2,

c_e(t_1)=1.

Then:

[ {e} ]

is infeasible at $t_0$ and feasible at $t_1$ .

Therefore there is no one fixed feasible family:

\mathcal F\subseteq2^I

representing both times.

But if the underlying utility is still:

F_{\mathrm{cov}},

that utility remains submodular.

Hence:

\boxed{ \text{dynamic cost does not necessarily break utility submodularity;} }

it breaks the static constrained-optimization formulation.

13. Why Deadline and Dynamic Cost Must Not Be Collapsed

Deadline value modifies:

\text{objective}.

Dynamic cost modifies:

\text{feasibility / resource state}.

The two can coexist but are mathematically distinct.

Treating both as:

"submodularity violation"

throws away useful structure.

14. Property Matrix

The machine-readable canonical matrix uses:

TRUE
FALSE
CONDITIONAL
NOT_APPLICABLE

The principal rows are:

Model	Static set function	Monotone	Submodular	Adaptive-submodular general	Order/time invariant	Static feasible family
Pure cascade coverage	TRUE	TRUE	TRUE	N/A	TRUE	TRUE
Mixed release, blocker ≤1	TRUE	FALSE	TRUE	N/A	TRUE	TRUE
Mixed release, multi-blocker	TRUE	FALSE	FALSE	N/A	TRUE	TRUE
Independent modular belief	Conditional	TRUE	TRUE	TRUE	TRUE	TRUE
Correlated belief update	Conditional	Conditional	Conditional	FALSE	Conditional	TRUE
Deadline value	FALSE	N/A	N/A	N/A	FALSE	Conditional
Dynamic cost only	TRUE	Conditional	Conditional	Conditional	Conditional	FALSE
Full Runtime	FALSE	N/A	N/A	FALSE	FALSE	FALSE

15. Breakdown Events Are Not All the Same

We can now distinguish four kinds of transition.

15.1 Property loss

Example:

\text{monotone} \to \text{non-monotone}.

15.2 Guarantee loss

Example:

|B_u|=1 \to |B_u|=2.

Some instances may remain submodular, but the universal theorem disappears.

15.3 Object-type change

Example:

\text{set utility} \to \text{sequence/time utility}.

15.4 Constraint-type change

Example:

\text{fixed knapsack} \to \text{dynamic feasibility}.

This is why the final object is a lattice rather than a scalar "complexity level".

16. Breakdown Lattice as a Runtime Router

The Runtime can now carry a structural certificate:

optimization_regime:
  utility:
    type: PURE_CASCADE_COVERAGE
    monotone: true
    submodular: true

  stochastic:
    belief_update: false

  temporal:
    deadline_value: false

  cost:
    dynamic: false

and choose a backend consistent with certified structure.

Example routes:

PURE_CASCADE_COVERAGE
→ monotone submodular optimizer candidate

MIXED_RELEASE + blocker<=1
→ non-monotone submodular optimizer candidate

MIXED_RELEASE + blocker>=2
→ generic combinatorial / exact / heuristic backend

CORRELATED_BELIEF_UPDATE
→ adaptive diagnostic required

DEADLINE
→ scheduling / sequence backend

DYNAMIC_COST
→ online/dynamic constrained backend

No route may be selected only because the word "submodular" appeared earlier in the lineage.

17. Relation to Classical Submodular Optimization

The classical static theory assumes a set function:

f:2^N\to\mathbb R.

Nemhauser, Wolsey, and Fisher analyze greedy approximation for nondecreasing submodular set functions under cardinality constraints.

The v0.8 pure cascade model fits this static family.

Once release interaction makes the function non-monotone, a different optimization literature is relevant.

Once stochastic observations affect future marginal values, adaptive submodularity is the relevant candidate notion — but only if its conditional diminishing-return property actually holds.

Once deadlines make order matter or costs change with time, the object is no longer the same static set-function problem.

18. Formal External Boundary

Golovin and Krause define adaptive submodularity as a diminishing-return property over partial realizations and show greedy-style guarantees when the property is satisfied.

DEST does not infer:

\text{belief update} \Rightarrow \text{adaptive submodular}.

Proposition 10 gives an explicit two-item counterexample.

This means correlation structure belongs inside the theorem assumptions, not in a footnote.

19. Exact Minimality Summary

\boxed{ \text{Monotonicity break: 2 deterministic nodes.} }

\boxed{ \text{Static submodularity break: 3 deterministic nodes.} }

\boxed{ \text{Adaptive-submodularity break: 2 stochastic items.} }

\boxed{ \text{Time-dependence break: 1 action + 2 clock states.} }

\boxed{ \text{Order-dependence break: 2 actions.} }

\boxed{ \text{Static feasible-family break: 1 action + dynamic cost.} }

20. Main conclusion

The v0.9 Breakdown Lattice replaces the vague statement:

Dynamic features break submodularity.

with a typed statement:

\boxed{ \text{release can break monotonicity;} }

\boxed{ \text{multiple blockers can break static submodularity;} }

\boxed{ \text{correlation can break adaptive submodularity;} }

\boxed{ \text{deadlines can replace set utility with sequence/time utility;} }

\boxed{ \text{dynamic cost can replace a fixed feasible family with dynamic feasibility.} }

The resulting boundary is substantially sharper than a binary "submodular / not submodular" label.

DEST therefore gains a new machine-checkable question:

Before selecting an optimization theorem or scheduler, what mathematical regime is the current verification-debt problem actually in?

That is the purpose of the Breakdown Lattice.