Verification Asymmetry in Optimal Transport

Optimal transport (OT) solvers often return a coupling that is subsequently used as a correspondence, alignment, or training target. We study a question distinct from computing that coupling: given a candidate and a declared proof language, how much evidence is needed to certify near-optimality or refute it? We introduce a candidate-specific, proof-language-relative verification profile with two sides: the interaction width of a positive certificate and the size of a replayable negative witness. These requirements can scale differently. Under coordinate-block proofs, a $d$-dimensional parity family requires full width $d$ to certify any optimal candidate to tolerance below $4$, while every full-support suboptimal candidate has a four-edge refutation. The positive obstruction persists under Wasserstein perturbations; on the negative side, some four-cycle has unit improvement margin at least half of the global suboptimality gap. We also show how local Kantorovich duals compose into global lower bounds, when certificate gaps control plan error, and when incomplete observations force abstention. VerifyOT returns Certified, Refuted, or Unknown. Theorem-aligned experiments recover the predicted width regimes and four-cycle bound. On Sinkhorn/Greenkhorn candidates, positive closure appears near the exact-OT regime, while every repaired full-support output in our audit admits an exact four-cycle refutation under the common unregularized cost.