Research map / Learning theory and algorithms / Combinatorial and search optimization
PREMAP: A Unifying PREiMage APproximation Framework for Neural Networks
Xiyue Zhang, Benjie Wang, Marta Kwiatkowska, Huan Zhang
Read the paperCheck your idea against 137,217 papers
AI-extracted. The measured effects below were read by AI from the paper's full text (no summary yet). Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| use PREMAP approximation instead of exact preimage computation | preimage generation · Vehicle Parking and VCAS | computation time: Exact 3174.709 s vs PREMAP 1.120 s (under-approx) on Vehicle; VCAS 6363.272 -> 10.775 | Improved |
| use PREMAP instead of exact preimage to describe the preimage | polytope count · Vehicle Parking | number of polytopes: average reduction of 69.2% | Improved |
| use PREMAP under-approximation instead of exact preimage | polytope count · VCAS | number of polytopes: 131 -> 15 (88.5% reduction) | Improved |
| use PREMAP over-approximation instead of exact preimage | polytope count · VCAS | number of polytopes: 131 -> 1 (99.2% reduction) | Improved |
| use PREMAP instead of Invprop for under-approximation | preimage under-approximation · Vehicle Parking | coverage ratio: 0.909 -> 0.945 (average Cov) | Improved |
| use PREMAP instead of Invprop for under-approximation time | preimage under-approximation · Vehicle Parking | time (s): 2.403 -> 1.120 | Improved |
| use Invprop instead of PREMAP for over-approximation | preimage over-approximation · Vehicle Parking | coverage ratio and time: PREMAP 1.081 vs Invprop 1.059 coverage; time 1.148 vs 0.840 | Hurt |
| add new input-feature splitting heuristic over prior method (ablation) | PREMAP refinement · preimage approximation | computation time to same precision: 49.7% (avg.) computation time of the prior method | Improved |
| add Lagrangian relaxation for neuron splitting constraints (ablation) | PREMAP · MNIST preimage approximation | precision: precision gains of up to 58.6% (avg.) | Improved |
Later papers that compared with this method
1 later accepted paper reports PREMAP as a baseline in their results tables; 1 of them report a better number on most of the results they share with it.
- On the Probabilistic Learnability of Compact Neural Network Preimage Bounds (AAAI 2026 · better on 7 of 12 shared results)
Matched by method name in results tables read by AI. Authors' own tables tend to favour the newer method, and a comparison can be missed when a method is renamed.
Closest papers by meaning
- Provably Bounding Neural Network Preimages (NeurIPS 2023 · similarity 0.88)
- Verification of Neural Networks Against Convolutional Perturbations via Parameterised Kernels (AAAI 2025 · similarity 0.87)
- Towards General Robustness Verification of MaxPool-based Convolutional Neural Networks via Tightening Linear Approximation (CVPR 2024 · similarity 0.85)
- Provable Editing of Deep Neural Networks using Parametric Linear Relaxation (NeurIPS 2024 · similarity 0.85)
- Tightening Robustness Verification of MaxPool-based Neural Networks via Minimizing the Over-Approximation Zone (CVPR 2025 · similarity 0.84)
- LEVIS: Large Exact Verifiable Input Spaces for Neural Networks (ICML 2025 · 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.
