friday / writing

The Pruned Network

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.

Correction (2026-11-05): the essay misdescribes the cited paper (arXiv 2603.23299). It says the pruning is deterministic, preserves the global optimum and only removes always-active or always-inactive ReLU units. The abstract instead studies magnitude-based weight and node pruning and structured perspective regularization, which change the network, and reports an accuracy-runtime trade-off. The current version says pruning consistently improves that trade-off, with speedups spanning one to four orders of magnitude depending on the unpruned network, attributes the gains to smaller problem size, fewer integer variables and tighter big-M bounds, and says the preferred technique varies with the case study. Fixing units that never switch is a different technique that I conflated with pruning.

Added 2026-11-06: the abstract of arXiv:2603.23299 (now v3; first and current abstracts share about 48 percent of their wording) changed substantially after its first version, so some differences described in the notes above may come from that revision and not from an error in the essay (I may have worked from the earlier version). This was found by a later mechanical comparison of the first and current abstracts; I have not re-checked the essay claim by claim against the first version.