SMT-Certified Loss-Preserving Network Rewrites
Source paper: SOVER: Formal Certification of Optimization Reformulations via LLM-Assisted SMT Verification arXiv:2609.00728 ⓘ · analyzed Sep 2, 2026
AI-generated research hypothesis, automatically tested. Not peer-reviewed.
Idea description
Represent an original neural-network block and a proposed rewritten block as constrained optimization formulations over inputs and trainable parameters, then certify that the rewrite preserves feasibility and the ordering of losses over a bounded domain. This gives a compiler or pruning pipeline a formal reject/accept gate instead of relying only on numerical regression tests.
Formulas
Mathematical statement
The paper defines a constrained minimization problem as $\min_{\mathbf{x}\in\mathcal{X}} f(\mathbf{x})$, with feasible region $\mathcal{X}$, and defines the optimizer set as $\argmin_{\mathbf{x}\in\mathcal{X}} f(\mathbf{x})=\{\mathbf{x}^{\star}\in\mathcal{X}\mid f(\mathbf{x}^{\star})\leq f(\mathbf{x}),\ \forall\mathbf{x}\in\mathcal{X}\}$. Two formulations are $\argmin$-equivalent when a mapping $\Sigma$ between feasible domains maps the minimizers of one formulation onto those of the other; equality of objective values is not required because a positive scaling or strictly increasing objective transformation preserves minimizers. For a neural rewrite, let $z$ denote bounded network inputs, $\theta$ the original parameters, $\tilde{\theta}=\Sigma(\theta)$ the transformed parameters, $\mathcal{X}$ and $\tilde{\mathcal{X}}$ the corresponding domains, and $\ell$ and $\tilde{\ell}$ the original and rewritten losses. The SMT certificate should establish domain cross-feasibility $\theta\in\mathcal{X}\Leftrightarrow\Sigma(\theta)\in\tilde{\mathcal{X}}$ and global objective-order preservation: $\ell(z,\theta_1)\leq\ell(z,\theta_2)\Leftrightarrow\tilde{\ell}(z,\Sigma(\theta_1))\leq\tilde{\ell}(z,\Sigma(\theta_2))$ for every bounded input $z$ and every admissible parameter pair. These conditions map minimizer sets rather than merely showing that one sampled training run has the same loss.
Implementation notes
Integrate this as a verification pass after a graph rewrite and before accepting the rewritten model for training or deployment. Start with a bounded MLP or transformer feed-forward block using affine layers, ReLU, clipping, masking, and parameter transformations such as channel permutation, neuron splitting, exact parameter tying, or removal of provably zero channels. Inputs are a box $z\in\mathcal{Z}=[-B,B]^d$; parameters are bounded by learned or user-specified intervals $\theta\in\mathcal{X}$. Build two symbolic expressions, loss_orig(z, theta) and loss_new(z, Sigma(theta)), using an SMT solver with linear real arithmetic plus ReLU encodings. First query the negation of cross-feasibility: exists theta: theta in X and Sigma(theta) not in Xnew, and reject if satisfiable. Then query the negation of order preservation by introducing two independent parameter copies and searching for loss_orig(theta1) <= loss_orig(theta2) XOR loss_new(Sigma(theta1)) <= loss_new(Sigma(theta2)); an UNSAT result is the certificate. If the loss contains squared error, either use a nonlinear solver for tiny blocks or certify the stronger pointwise equality network_orig(z,theta)=network_new(z,Sigma(theta)). The paper supplies the logical equivalence criterion; interval bounds, the input box, and solver encodings are engineering choices. Begin with CIFAR-10, a two-layer ReLU MLP, and exact neuron-permutation/channel-pruning rewrites. Compare against ordinary random regression tests on 10,000 inputs. Success means zero counterexamples on certified cases, immediate detection of deliberately incorrect rewrites, and no measurable accuracy change after accepted transformations.
Verification
This idea has not been verified yet.
Verification happens in two stages: Stage 1 — a mechanism check on a toy system confirms the claimed mathematical phenomenon reproduces; Stage 2 — a benchmark implements the idea on a real (small) neural network task and compares it against a tuned baseline over 8 paired seeds with a permutation test.
Artifacts
Artifacts unavailable.