Skip to content

coalition_eval: merge-only joins provably need no slow re-inversion (skip the O(m³) path) #208

Description

@tsondru

Split out of #153's measurement round (design memo of 2026-08-02; closing record on #153 has the summary).

The measured fact

For candidates where the skeletal-merge test fires WITHOUT interior improvement — (∃i: c[i]==1.0 ∧ r[i]==1.0) ∧ ¬(∃i≠j: c[i]·r[j] > closed[i][j]) — the join provably contributes zero diversity: Mag(S ∪ {x}) = Mag(S) exactly, as a real number. Measured across the #153 sweep: 268/268 such candidates return a value bitwise-equal to base_value() on both the incremental and fresh routes.

Yet value_with currently routes every merge candidate through value_with_slow: an O(m²) re-border + re-skeletalize + O(k³) re-inversion — all to compute a number we can prove equals the cached base_mag before doing any of it. Since #153 (PR #207) the predicate is already computed and named in value_with_core (it feeds ZeroDiversityProof::SkeletalMerge).

Why this is its own issue, not part of #153

Short-circuiting merge-only → return base_mag changes error behaviour: the slow path can currently Err (singular re-inversion), and error-parity with fresh evaluation is a documented #31 contract point (the module's seeded_grid_fresh_vs_incremental asserts it). The #153 measurements suggest a merge-only bordered ζ′ is singular iff ζ_S is (det ζ′ = det ζ_S · s with the merged structure), i.e. the short-circuit may be error-parity-safe — but that claim was NOT part of the #153 evidence base and needs its own argument + sweep before shipping.

Scope sketch

Metadata

Metadata

Assignees

No one assigned

    Labels

    No labels
    No labels

    Type

    No type

    Projects

    No projects

      Milestone

      No milestone

      Relationships

      None yet

      Development

      No branches or pull requests

      Issue actions