Research map / Learning theory and algorithms / Combinatorial and search optimization
Provable Editing of Deep Neural Networks using Parametric Linear Relaxation
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 PREPARED, a polynomial-time LP-based method for provably editing DNN parameters to satisfy input/output polytope properties, using Parametric Linear Relaxation of layers.
Problem
Provably editing a DNN's parameters so that all inputs in an input polytope map into a desired output polytope, with minimal parameter change; prior approaches are either unsound (regularization), NP-hard (SMT), or restricted (LP-based with vertex/linear-region enumeration).
Approach
Constructs parametric linear relaxations whose upper/lower output bounds are exact epigraph/hypograph constraints expressed in terms of the editable parameters (not constant bounds), so the whole provable editing problem becomes a single polynomial-size LP.
Key results
- On VNN-COMP'22, PREPARED succeeded on all 423 single-property editing problems versus 185 for PFT<DL2> and 117 for PFT<APRNN>, finishing in at most 45 seconds.
- On CIFAR10 local robustness, PREPARED reached 50/50 efficacy with 75.25% standard and 71.45% certified accuracy in 88s, while APRNN achieved only 5/50 efficacy.
- On SST BERT local robustness, PREPARED was the only method reaching 100% efficacy in both settings (66/66 at eps=1e-4 and 26/26 at eps=5e-4).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use PREPARED instead of verifier-in-the-loop PFT baselines | VNN-COMP′22 editing · single-property editing | instances succeeded: 185 -> 423; 117 -> 423 | Helped |
| Use PREPARED instead of verifier-in-the-loop PFT baselines | VNN-COMP′22 editing · all-properties editing | instances succeeded: 45 -> 62; 48 -> 62 | Helped |
| Use PREPARED instead of PFT⟨SABR⟩ | CNN7 · CIFAR10 local robustness, ε=0.5/255 | standard accuracy: 57.10% -> 75.25% | Helped |
| Use PREPARED instead of PFT⟨SABR⟩ | CNN7 · TINYIMAGENET local robustness, ε=1/255 | standard accuracy: 20.24% -> 28.16% | Helped |
| Use PREPARED instead of APRNN | CNN7 · CIFAR10 local robustness, ε=0.5/255 | efficacy: 5/50 -> 50/50 | Helped |
| Use PREPARED instead of APRNN | CNN7 · TINYIMAGENET local robustness, ε=1/255 | efficacy: 12/50 -> 50/50 | Helped |
| Use PREPARED instead of PFT⟨DL2⟩ | 12-layer BERT · SST local robustness, ε=1e-4 | efficacy: 52/66 -> 66/66 | Helped |
| Use PREPARED instead of PFT⟨DL2⟩ | 12-layer BERT · SST local robustness, ε=5e-4 | efficacy: 23/26 -> 26/26 | Helped |
Surprising findings
- PFT<DL2> failed to reach 100% efficacy on TinyImageNet even after a four-hour timeout.
- APRNN decreased efficacy on several BERT editing sets rather than improving it.
Limitations
- Properties must be formally specified, which may be hard for complex properties such as LLM safety.
- Editing restricted to last k layers for scalability; the approach is LP-based and bounded by Gurobi solver performance.
- Accuracy on VNN-COMP benchmarks could not be measured because no accuracy data is provided.
Experimental setup
Datasets: VNN-COMP'22 benchmarks CIFAR10 CIFAR10-C TinyImageNet TinyImageNet-C Stanford Sentiment Treebank geodynamics numerical simulation data
Benchmarks: VNN-COMP'22 benchmarks CIFAR10 TinyImageNet SST (BERT) geodynamics physics constraints
Metrics: efficacy standard accuracy certified accuracy generalization accuracy runtime relative error continuity error boundary-condition error
Baselines: PFT<DL2> PFT<APRNN> PFT<SABR> PFT<STAPS> APRNN GD
Builds on: DL2 APRNN PRDNN DeepPoly DeepT
Closest papers by meaning
- Verification of Neural Networks Against Convolutional Perturbations via Parameterised Kernels (AAAI 2025 · similarity 0.86)
- Clip-and-Verify: Linear Constraint-Driven Domain Clipping for Accelerating Neural Network Verification (NeurIPS 2025 · similarity 0.85)
- VNN: Verification-Friendly Neural Networks with Hard Robustness Guarantees (ICML 2024 · similarity 0.85)
- Gradient Rewiring for Editable Graph Neural Network Training (NeurIPS 2024 · similarity 0.85)
- Practical Performance Guarantees for Pipelined DNN Inference (ICML 2024 · similarity 0.85)
- Improving robustness to corruptions with multiplicative weight perturbations (NeurIPS 2024 · similarity 0.84)
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.