Research map / Learning theory and algorithms / Combinatorial and search optimization
Dynamic Back-Substitution in Bound-Propagation-Based Neural Network Verification
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes Dynamic Back-Substitution SIP (DBS-SIP), which uses fast-propagated intermediate bounds to detect stable ReLUs during back-substitution and drop their equations, giving lossless speedups for neural network verification.
Problem
Bound-propagation-based neural network verification via symbolic interval propagation with back-substitution is computationally expensive, especially for large and deep networks, and progress on its efficiency has slowed.
Approach
At each back-substitution step, fast-propagate symbolic bounds to the input to identify stable ReLU neurons and remove their equations from the coefficient matrix, reducing cost without precision loss; a cost-benefit heuristic decides when to apply it.
Key results
- On TinyYOLO with epsilon 1e-4, dynamic back-substitution with the heuristic cut runtime by 51.25% (14682 to 1470 ... 3016 vs 1470 seconds).
- On ResNet34 with brightness epsilon 1e-5, runtime fell 35.41% (46238 to 29866) in incomplete verification; gains up to about 40% reported for large models.
- Without the heuristic, the method gave no gains on cifar biasfield and no gains on ResNet34, showing the heuristic is essential.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Apply dynamic ReLU-stability inference during back-substitution with the heuristic | BS-SIP on TinyYOLO · TinyYOLO, brightness ε=10−4 | runtime: 3016 -> 1470 | Helped |
| Apply dynamic ReLU-stability inference during back-substitution with the heuristic | BS-SIP on ResNet18 · ResNet18, brightness ε=10−5 | runtime: 11643 -> 7152 | Helped |
| Apply dynamic ReLU-stability inference during back-substitution with the heuristic | BS-SIP on ResNet34 · ResNet34, brightness ε=10−5 | runtime: 46238 -> 29866 | Helped |
| Apply dynamic ReLU-stability inference during back-substitution with the heuristic | BS-SIP on cifar biasfield · cifar biasfield, bias fields ε=10−2 | runtime: 1114 -> 1316 | Hurt |
| Apply dynamic ReLU-stability inference during back-substitution with the heuristic | BS-SIP on cifar biasfield · cifar biasfield, bias fields ε=10−5 | runtime: 89 -> 89 | No clear effect |
| Disable the heuristic and attempt to stabilise all unstable nodes at every back-substitution step (ablation) | DBS-SIP on cifar biasfield · cifar biasfield, bias fields ε=6 · 10−2 | runtime: 1708 -> 1843 | Hurt |
| Disable the heuristic and attempt to stabilise all unstable nodes at every back-substitution step (ablation) | DBS-SIP on ResNet18 · ResNet18, brightness ε=10−4 | runtime: 16056 -> 14578 | Hurt |
| Disable the heuristic and attempt to stabilise all unstable nodes at every back-substitution step (ablation) | DBS-SIP on ResNet34 · ResNet34, brightness ε=10−4 | runtime: 52851 -> 52923 | Hurt |
Surprising findings
- Without the governance heuristic, dynamic back-substitution often increases runtime, so the overhead of stability inference can outweigh savings.
- Gains shrink or reverse for large perturbations (e.g., cifar biasfield at epsilon 1e-2), where few ReLUs are stabilised.
Limitations
- Gains are minimal or negative for small models and large perturbation sizes due to heuristic overhead.
- Complete-verification gains are diluted by timeouts; reported gains up to 27% only for ResNet18.
Experimental setup
Datasets: VNNComp 2022 cifar biasfield benchmark VNNComp 2023 TinyYOLO benchmark randomly generated verification properties for ResNet18/ResNet34
Benchmarks: VNNComp 2022 cifar biasfield VNNComp 2023 TinyYOLO ResNet18 brightness perturbation ResNet34 brightness perturbation
Metrics: runtime percentage runtime change number of verified queries timeouts
Baselines: standard back-substitution BS-SIP DBS-SIP without heuristic Venus
Builds on: symbolic interval propagation back-substitution (Neurify/CROWN-style general activation bounds) Venus verifier forward SIP (ReluVal/Neurify)
Closest papers by meaning
- Clip-and-Verify: Linear Constraint-Driven Domain Clipping for Accelerating Neural Network Verification (NeurIPS 2025 · similarity 0.89)
- SDP-CROWN: Efficient Bound Propagation for Neural Network Verification with Tightness of Semidefinite Programming (ICML 2025 · similarity 0.88)
- DeepBern-Nets: Taming the Complexity of Certifying Neural Networks Using Bernstein Polynomial Activations and Precise Bound Propagation (AAAI 2024 · similarity 0.86)
- Scalable Neural Network Verification with Branch-and-bound Inferred Cutting Planes (NeurIPS 2024 · similarity 0.86)
- Dynamic Algorithm Termination for Branch-and-Bound-based Neural Network Verification (AAAI 2025 · similarity 0.85)
- Verifying message-passing neural networks via topology-based bounds tightening (ICML 2024 · similarity 0.85)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.