DEST v0.8 — Fixed-Cost Certificate Cascade Model

Weighted-Coverage Theorem, Exact Small-DAG Census, and Minimal Mixed-Utility Counterexamples

Version: v0.1
Date: 2026-08-14
Engineering parent: DEST Runtime v0.7-alpha
Status: theorem-style mathematical submodel + executable exhaustive checks

Abstract

DEST Runtime v0.7-alpha empirically separated three regimes:

pure certificate-cascade structure;
belief-conditioned evidence transfer;
deadline/dynamic-cost scheduling.

On its frozen holdout, sampled diminishing-return violations were:

[ 0/30000 ]

for the pure structural cascade,

[ 1963/30000 ]

after belief transfer, and

[ 20309/30000 ]

after deadline/dynamic-cost effects.

This paper asks whether the first zero-violation result reflects a genuine theorem.

The answer is yes, but only after separating two different utilities that v0.7 had combined.

Pure Cascade Coverage

Let every inspection (i) have a fixed deterministic affected set $A_i$ , and let every affected certificate/debt target (v) have a fixed nonnegative weight $w_v$ . Define:

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

Then $F_{\mathrm{cov}}$ is a weighted coverage function and therefore is:

\boxed{ \text{normalized, monotone, and submodular}. }

For certificate DAGs, $A_i$ may be the descendant closure of certificate (i). The proof does not actually require acyclicity; it requires only that each action's affected set be fixed independently of the selected set and history.

Mixed Revoke–Release Utility

The v0.7 structural runtime additionally gave value to confirming a valid quarantined node, but removed that release value when an invalid ancestor revoked it.

That creates terms of the form:

h_u(S) = r_u \mathbf 1[u\in S] \mathbf 1[S\cap B_u=\varnothing],

where $B_u$ is the set of invalid inspections whose cascade blocks the release of valid node (u).

This term is not universally submodular when:

|B_u|\ge 2.

A three-node counterexample exists.

Therefore:

\boxed{ \text{Pure certificate cascade is a weighted-coverage submodular model;} }

but:

\boxed{ \text{the full mixed revoke–release utility is not generally submodular.} }

The paper proves a useful sufficient condition:

\boxed{ |B_u|\le1 \quad\forall u\text{ with }r_u>0 }

implies that the mixed utility remains submodular, though it need not be monotone.

An exact exhaustive program accompanies this paper. It enumerates every ordered DAG up to $n=5$ , representing every finite DAG structure up to a topological relabeling, and checks the pure coverage diminishing-return inclusion property. It also searches all valid/invalid status assignments for minimal mixed-utility counterexamples.

1. Why v0.8 exists

The goal is not to claim that the complete DEST Runtime is submodular.

v0.7 already falsified that.

Instead, v0.8 asks:

Which exact substructure generated the zero-violation empirical signal?

This is an inversion of the usual workflow:

Runtime experiment
→ structural regularity
→ mathematical isolation
→ theorem
→ exact census
→ minimal counterexample to overgeneralization

2. Fixed Cascade Model

Let:

I=\{1,\ldots,m\}

be a finite inspection/action set and:

U=\{1,\ldots,n\}

be a finite target universe.

Each inspection $i\in I$ has a fixed affected set:

A_i\subseteq U.

Each target $u\in U$ has weight:

w_u\ge0.

For selected inspections $S\subseteq I$ , define:

C(S)=\bigcup_{i\in S}A_i.

Then:

F_{\mathrm{cov}}(S) = \sum_{u\in C(S)}w_u.

For a certificate DAG $G=(V,E)$ , one canonical choice is:

I=U=V

and:

A_i=\operatorname{Desc}^{+}(i),

the node together with every deterministic downstream certificate invalidated by the cascade.

3. Theorem 1 — Normalization

\boxed{ F_{\mathrm{cov}}(\varnothing)=0. }

Proof

C(\varnothing)=\varnothing.

Therefore the weighted sum over the covered set is zero. $\square$

4. Theorem 2 — Monotonicity

If:

S\subseteq T,

then:

\boxed{ F_{\mathrm{cov}}(S)\le F_{\mathrm{cov}}(T). }

Proof

Because union is monotone:

\bigcup_{i\in S}A_i \subseteq \bigcup_{i\in T}A_i.

All $w_u$ are nonnegative, so adding covered targets cannot decrease total weight. $\square$

5. Theorem 3 — Submodularity

For:

S\subseteq T\subseteq I, \qquad e\in I\setminus T,

define marginal gain:

\Delta(e\mid S) = F_{\mathrm{cov}}(S\cup\{e\})-F_{\mathrm{cov}}(S).

Then:

\boxed{ \Delta(e\mid S)\ge \Delta(e\mid T). }

Proof

The newly covered targets after adding (e) to (S) are:

N_S(e) = A_e \setminus \bigcup_{i\in S}A_i.

Similarly:

N_T(e) = A_e \setminus \bigcup_{i\in T}A_i.

Since:

S\subseteq T,

we have:

\bigcup_{i\in S}A_i \subseteq \bigcup_{i\in T}A_i.

Hence:

N_T(e)\subseteq N_S(e).

Therefore:

\Delta(e\mid S) = \sum_{u\in N_S(e)}w_u \ge \sum_{u\in N_T(e)}w_u = \Delta(e\mid T).

Thus $F_{\mathrm{cov}}$ is submodular. $\square$

6. Corollary — The DAG is not the source of submodularity

The proof uses only:

A_i\text{ fixed}

and:

w_u\ge0.

Therefore acyclicity is not necessary for the set-function theorem.

The DAG remains important to DEST because:

it encodes certificate semantics;
it gives a natural downstream closure;
it supports revocation provenance and replay.

But the mathematical source of submodularity is:

\boxed{ \text{fixed weighted set coverage}. }

7. Fixed Costs

Assign every inspection a fixed cost:

c_i>0.

A budget constraint is:

\sum_{i\in S}c_i\le B.

This changes the feasible family of sets, not the utility:

F_{\mathrm{cov}}.

Therefore:

\boxed{ \text{fixed costs do not destroy utility submodularity}. }

They change the optimization problem from cardinality-constrained selection to a knapsack-type constraint.

For equal costs / cardinality (k), the classical monotone-submodular greedy result of Nemhauser, Wolsey, and Fisher applies to this model. This paper does not claim the same bound for naive cost-ratio greedy under arbitrary costs.

8. Why v0.7's full structural utility is different

v0.7 also modeled valid quarantined claims.

Let:

$I^-$ : inspections with deterministic invalid outcomes;
$I^+$ : inspections with deterministic valid outcomes.

Invalid inspection $a\in I^-$ revokes a fixed closure $A_a$ .

For each valid node $u\in I^+$ , define blocker set:

B_u = \{ a\in I^-: u\in A_a \}.

A valid inspection (u) receives release value $r_u\ge0$ only if no selected invalid blocker revokes it:

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

The mixed utility is:

F_{\mathrm{mix}}(S) = F_{\mathrm{revocation}}(S\cap I^-) + \sum_{u\in I^+}h_u(S).

The first term is weighted coverage and is submodular.

The second term is where the theorem can break.

9. Proposition 4 — Monotonicity is not guaranteed

Consider two inspections:

a\to u,

where (a) is invalid and (u) is valid.

Let:

r_u=1, \qquad w_a=0.1.

Then:

F_{\mathrm{mix}}(\{u\})=1,

while:

F_{\mathrm{mix}}(\{a,u\})=0.1.

Thus:

F_{\mathrm{mix}}(\{a,u\}) < F_{\mathrm{mix}}(\{u\}).

Therefore mixed revoke–release utility need not be monotone. $\square$

10. Lemma 5 — A release term with zero blockers is modular

If:

B_u=\varnothing,

then:

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

This is modular, hence submodular. $\square$

11. Lemma 6 — A release term with one blocker is submodular

Suppose:

B_u=\{a\}.

Then:

h_u(S) = r_u\mathbf1[u\in S]\mathbf1[a\notin S].

The only nonzero positive marginal is adding (u) before blocker (a) is selected.

Adding (a) has marginal:

-r_u

when (u) is present and zero otherwise.

For every:

S\subseteq T, \qquad e\notin T,

the marginal at (T) never exceeds the marginal at (S).

Hence $h_u$ is submodular. $\square$

12. Theorem 7 — Blocker-At-Most-One Sufficient Condition

If:

\boxed{ |B_u|\le1 \quad \forall u\in I^+\text{ with }r_u>0, }

then:

\boxed{ F_{\mathrm{mix}} \text{ is submodular}. }

Proof

The revocation term is a weighted coverage function, hence submodular.

By Lemmas 5 and 6, every release term $h_u$ is submodular.

A finite sum of submodular functions is submodular.

Therefore $F_{\mathrm{mix}}$ is submodular. $\square$

This theorem does not imply monotonicity.

13. Proposition 8 — Two blockers destroy the universal guarantee

Suppose a valid node (u) has two distinct blockers:

a,b\in B_u, \qquad a\neq b,

and:

r_u>0.

Consider only the release term $h_u$ .

Set:

S=\{u\}, \qquad T=\{u,b\}, \qquad e=a.

Then:

\Delta_{h_u}(a\mid S)=-r_u,

because adding (a) removes the release of (u).

But (u) is already blocked in (T), so:

\Delta_{h_u}(a\mid T)=0.

Submodularity would require:

-r_u\ge0,

which is false.

Thus $h_u$ is not submodular.

Therefore if any positive-release valid node has two blockers, no universal submodularity guarantee exists for all nonnegative revocation weights: choose those revocation weights to be zero, or sufficiently small, and the violation survives. $\square$

14. Universal Characterization for the Mixed Model

For the model class in which revocation coverage weights may be arbitrary nonnegative values:

\boxed{ F_{\mathrm{mix}} \text{ is guaranteed submodular for every such weight assignment} }

if and only if:

\boxed{ |B_u|\le1 \quad \forall u\text{ with }r_u>0. }

The forward direction is Theorem 7.

The reverse universal statement follows from Proposition 8.

15. Minimal counterexamples

15.1 Non-monotonicity

Minimum ground-set size:

\boxed{2}.

Structure:

a (invalid)
|
v
u (valid release)

Selecting (u) first produces release value.

Adding (a) removes it.

15.2 Non-submodularity

Minimum ground-set size:

\boxed{3}.

Structure:

a (invalid) ─┐
             ├─> u (valid release)
b (invalid) ─┘

With:

S=\{u\}, \quad T=\{u,b\}, \quad e=a,

the marginal of (a) rises from negative to zero after more information/actions have already blocked (u).

That is increasing returns, not diminishing returns.

16. Exact Small-DAG Census

The accompanying program performs two exact censuses:

pure coverage: every forward-edge DAG on $n\le5$ ;
mixed valid/invalid assignment regression: every forward-edge DAG and assignment on $n\le4$ satisfying the tested scope.

The smaller mixed cutoff is an execution bound, not a theorem bound.

For fixed topological labels, the number of DAG edge sets is:

\sum_{n=1}^{5} 2^{n(n-1)/2} = 1+2+8+64+1024 = 1099.

Every finite DAG admits a topological ordering, so every DAG structure can be relabeled into this forward-edge representation.

For pure coverage, the program checks the stronger set inclusion:

N_T(e)\subseteq N_S(e)

for every:

S\subseteq T, \qquad e\notin T.

This implies diminishing returns for every nonnegative weight vector, not merely one sampled weight assignment.

The program separately:

finds the minimum non-monotone mixed model;
finds the minimum non-submodular mixed model;
exhaustively checks all status assignments through $n\le4$ satisfying $|B_u|\le1$ with deterministic positive regression weights.

The theorem for arbitrary nonnegative weights is analytic; the mixed census is a regression companion rather than its proof.

16.1 Exact census result

The completed executable census reports:

Pure cascade coverage

ordered DAGs through $n\le5$ : 1099;
exact $S\subseteq T,e\notin T$ new-coverage inclusion checks: 421861;
violations: 0.

Full mixed model at $n\le4$

Using fixed positive regression weights

w_{\mathrm{invalid}}=0.1, \qquad r_{\mathrm{release}}=1.0,

the census contains 1098 complete DAG/status models.

Among them:

537 are non-monotone;
160 are non-submodular;
exactly 160 contain at least one positive-release valid node with two or more invalid blockers;
all 160/160 of those models are non-submodular under this fixed regression weight assignment.

Blocker-at-most-one regression region

The $n\le4$ census contains 938 models satisfying $|B_u|\le1$ for every valid release node. Observed submodularity violations: 0/938.

This computational result is consistent with Theorem 7. The proof, not the census, carries the arbitrary-weight claim.

Minimal exact witnesses

The first non-monotone model has two nodes:

0 invalid -> 1 valid

with $F(\{1\})=1$ and $F(\{0,1\})=0.1$ .

The first non-submodular model has three nodes:

0 invalid -> 1 invalid -> 2 valid

where valid node 2 has blockers $B_2=\{0,1\}$ . The exact witness is

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

with

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

Thus even a single chain, rather than a branching fork, is enough to destroy the universal mixed-utility guarantee.

17. Belief Transfer

Once inspection results update another debt's estimated probability:

p_j \to p_j',

the objective becomes history-conditioned.

It is no longer represented by one fixed set function:

F:2^I\to\mathbb R.

Classical submodularity is therefore no longer automatically the right object.

One may ask whether an adaptive-submodular model exists, but only after specifying:

outcome space;
partial realizations;
conditional expected marginal values;
prior;
observation model.

v0.7 empirically observed nonzero diminishing-return violations after belief transfer.

Therefore DEST currently has no general adaptive-submodularity theorem.

18. Deadlines and Dynamic Costs

If the score of inspection (i) depends on clock time:

Score_i(t),

then the same selected set can have different value depending on ordering and time.

Likewise:

c_i=c_i(t)

changes the feasible continuation as time evolves.

Thus the full runtime is not one static set-function maximization problem unless time is explicitly encoded into the state/ground elements.

v0.7's high violation rate in the deadline/dynamic-cost diagnostic is therefore not surprising: the fixed-set diminishing-return law is being tested outside its natural static scope.

19. What v0.8 proves

\boxed{ \textbf{Theorem A:} \quad \text{Fixed deterministic certificate cascade coverage with nonnegative target weights is normalized, monotone, and submodular.} }

\boxed{ \textbf{Theorem B:} \quad \text{Fixed inspection costs preserve utility submodularity.} }

\boxed{ \textbf{Theorem C:} \quad |B_u|\le1\ \forall u \text{ is sufficient for mixed revoke–release submodularity.} }

\boxed{ \textbf{Counterexample D:} \quad \text{mixed revoke–release utility is not monotone in general.} }

\boxed{ \textbf{Counterexample E:} \quad \text{two blockers of one positive-release valid node are enough to destroy the universal submodularity guarantee.} }

20. What v0.8 does not prove

It does not prove:

full DEST is submodular;
full DEST is adaptive submodular;
v0.7 scheduler has a greedy approximation guarantee;
deadline urgency preserves submodularity;
probability calibration preserves adaptive diminishing returns;
dynamic costs preserve an approximation factor;
branch interactions can always be reduced to coverage;
quarantine release is harmless to monotonicity.

21. External alignment

Coverage functions are a standard special case of submodular functions.

The classical Nemhauser–Wolsey–Fisher analysis studies greedy maximization of nondecreasing submodular set functions under a cardinality constraint and obtains the familiar limiting (1-1/e) guarantee.

Adaptive submodularity generalizes diminishing returns to partial observations, but its guarantees require its structural assumptions to hold.

DEST v0.8 uses these theories only where their hypotheses match the isolated submodel.

22. Engineering consequence

The Runtime should stop asking:

Is DEST submodular?

The correct question is:

Which utility components are submodular, which are not, and which runtime transitions move us between those classes?

This suggests a future scheduler can route by certified structural regime:

PURE_CASCADE_COVERAGE
  → monotone submodular backend allowed

MIXED_RELEASE, blocker_count <= 1
  → submodular but possibly non-monotone backend

MIXED_RELEASE, blocker_count >= 2
  → no universal submodularity guarantee

BELIEF_UPDATE
  → adaptive diagnostic required

DEADLINE / DYNAMIC_COST
  → state/time-dependent optimization backend

23. Final conclusion

The empirical zero-violation signal from v0.7 was real, but its correct interpretation was narrower than:

\text{DEST is submodular}.

What survives mathematical isolation is:

\boxed{ \text{fixed deterministic certificate cascade} = \text{weighted coverage}. }

And therefore:

\boxed{ \text{normalized} + \text{monotone} + \text{submodular}. }

The first principled break occurs not merely because "AI is dynamic", but already in a three-node deterministic mixed utility:

\boxed{ \text{two revocation blockers} + \text{one positive release value}. }

That gives DEST a sharper mathematical boundary:

\boxed{ \text{cascade coverage is the theorem region;} }

\boxed{ \text{release interaction is the first deterministic counterexample region;} }

\boxed{ \text{belief, deadlines, and dynamic costs belong to still richer state-dependent regimes.} }

This is the first point in the Runtime engineering line where an empirical regularity has been compressed into a theorem and then deliberately surrounded by exact counterexamples.

DEST v0.8 — Fixed-Cost Certificate Cascade Model

DEST v0.8 — Fixed-Cost Certificate Cascade Model

Weighted-Coverage Theorem, Exact Small-DAG Census, and Minimal Mixed-Utility Counterexamples

Abstract

Pure Cascade Coverage

Mixed Revoke–Release Utility

1. Why v0.8 exists

2. Fixed Cascade Model

3. Theorem 1 — Normalization

Proof

4. Theorem 2 — Monotonicity

Proof

5. Theorem 3 — Submodularity

Proof

6. Corollary — The DAG is not the source of submodularity

7. Fixed Costs

8. Why v0.7's full structural utility is different

9. Proposition 4 — Monotonicity is not guaranteed

10. Lemma 5 — A release term with zero blockers is modular

11. Lemma 6 — A release term with one blocker is submodular

12. Theorem 7 — Blocker-At-Most-One Sufficient Condition

Proof

13. Proposition 8 — Two blockers destroy the universal guarantee

14. Universal Characterization for the Mixed Model

15. Minimal counterexamples

15.1 Non-monotonicity

15.2 Non-submodularity

16. Exact Small-DAG Census

16.1 Exact census result

Pure cascade coverage

Full mixed model at n≤4n\le4n≤4

Blocker-at-most-one regression region

Minimal exact witnesses

17. Belief Transfer

18. Deadlines and Dynamic Costs

19. What v0.8 proves

20. What v0.8 does not prove

21. External alignment

22. Engineering consequence

23. Final conclusion

Full mixed model at $n\le4$