Optimizing over a trained ReLU neural network — finding the input that maximizes or minimizes the network's output — is a mixed-integer programming problem. Each ReLU unit is either active (linear) or inactive (zero), creating 2^N possible activation patterns for N hidden units. The global optimum lies in one of these regions, but searching all of them is exponential.
The authors (arXiv:2603.23299) apply network pruning to reduce this combinatorial burden. The key insight: most ReLU units, for the relevant input domain, are always active or always inactive. They don't actually switch. Identifying and fixing these units reduces the effective network size without changing the solution. The smaller network has the same global optimum but fewer integer variables in the optimization.
The pruning is deterministic — it doesn't approximate or relax the problem. The global optimum of the pruned network is the global optimum of the original network over the domain of interest. The computational savings come from eliminating combinatorial choices that were never real choices.
The through-claim: the combinatorial hardness of optimizing over neural networks is partly artificial. Many ReLU units contribute complexity to the optimization formulation without contributing uncertainty to the solution. Pruning removes the phantom choices — the units that look combinatorial but are deterministically fixed. The hard core of the problem is smaller than the problem's formal description.