Pruning removes most of a trained network's weights while keeping its accuracy. Methods with real guarantees treat each layer as a graph and keep the graph's "spectrum", meaning the eigenvalues of its Laplacian. The Laplacian is a matrix that summarizes how signal can flow between connected nodes, and keeping its spectrum keeps the paths through the network intact. In practice these methods hold accuracy at sparsity levels where simple magnitude pruning breaks. The catch is that they leave scattered individual zeros, which phones, edge GPUs, microcontrollers and accelerators cannot skip efficiently, so the network is smaller on paper but no faster on the device. Hardware-aware architecture search has the opposite problem. It measures real latency and memory well, but it has no principled signal for which cuts are safe for accuracy, and it needs either expensive supernet training or hand-tuned penalty weights.
We propose to make spectral sparsification produce only patterns the target device can execute, and to choose those patterns per layer under a measured latency budget. The patterns are whole blocks of weights, N:M groups, or entire channels. The key observation is that both quantities in this choice split cleanly over layers. Spectral sparsification of a deep network can be done layer by layer without loss relative to doing it globally (One-Shot Neural Network Pruning via Spectral Graph Sparsification). Device latency is well approximated by a sum of per-layer lookup-table entries (HW-NAS-Bench). Together these turn hardware-aware sparsity search into a small combinatorial problem that can be solved exactly in seconds. It needs no supernet, no penalty weight to tune, and no learned latency predictor.
Core Claim
The claim is that, at an equal measured latency on a specific device, a network pruned by hardware-shaped spectral sparsification will be more accurate than three alternatives: a network pruned by greedy structured saliency pruning, a network whose per-layer budgets are set by empirically measured layer sensitivity, and a dense, narrower network found by constraint-guided architecture search. The claim covers deep pruning ratios in particular, where layer collapse begins. It is falsifiable on all three counts, and the third comparison is the one that matters most.
The mechanism has three parts.
Coarsened layer graph. For each layer we build the bipartite graph between input and output neurons. We then coarsen it by grouping neurons into the tile shape the hardware actually computes. A tile is one block of weights in a block-sparse matrix multiply, or one full channel. The weight on each super-edge is the summed saliency score of the weights inside that tile.
Block sampling by effective resistance. Effective resistance treats each edge as a resistor and measures how much of a bottleneck it is. We sample whole super-edges in proportion to their effective resistance on the coarsened graph, in the style of Laenen's sparsifier. The result is a pattern that is executable by construction.
Per-layer allocation. For each layer $l$ and each candidate configuration $c$, which pairs a tile format with a density, we record two numbers. The first is the spectral distortion $\varepsilon_l(c)$, the measured worst-case relative change in the layer Laplacian's quadratic form. The second is the device latency $T_l(c)$, taken from a lookup table we measure on the device. We then solve
$$\min_{c_1,\dots,c_L}\ \max_{l}\ \varepsilon_l(c_l) \quad \text{s.t.} \quad \sum_{l=1}^{L} T_l(c_l) \le T,$$
where $L$ is the number of layers and $T$ is the latency budget. The max reflects our reading of the layerwise-to-global result: the whole network's spectral guarantee is governed by its worst layer. This objective can be solved exactly by bisection on $\varepsilon$. At each trial value we pick, for every layer, the cheapest configuration whose distortion stays below it, and we check whether the summed latency fits. A sum-of-distortions version, solved as a multiple-choice knapsack by dynamic programming, serves as an ablation.
Relation to Prior Work
Two lines of work motivate the gap from opposite sides.
Laenen's layerwise sparsifier (One-Shot Neural Network Pruning via Spectral Graph Sparsification) provides both the sampling method and the decomposition result we rely on. It shows that spectral sampling keeps the second Laplacian eigenvalue $\lambda_2$, a measure of how well connected the graph is, from collapsing at high sparsity, where greedy magnitude, SNIP and SynFlow pruning fail. However, it outputs unstructured masks, reaches arbitrary densities by rescaling probabilities heuristically, and never measures runtime. The research file names exactly this hardware-agnosticism as an open limitation of the whole spectral line.
UNIFEWS (Unifews) and StructSAM (StructSAM) show that spectral-similarity arguments do yield real speedups. UNIFEWS reports 10–20× fewer floating-point operations on ogbn-papers100M, and StructSAM reports 25–40% fewer encoder operations in Segment Anything. Both, however, target fixed models and count operations or server throughput rather than the cost on a specific device.
On the hardware side, HW-NAS-Bench (HW-NAS-Bench) constrains our evaluation. It shows that FLOP counts rank latency poorly, with a Kendall correlation as low as 0.18 on the Edge TPU, and that models tuned for one device transfer badly to another. We therefore measure latency on each device rather than proxying it. The same benchmark validates additive block-level latency tables for the FBNet search space, which is the assumption our solver depends on. We must re-check that assumption for sparse kernels.
ConNAS (Constraint-guided Hardware-aware NAS through Gradient Modification) and DUCCIO (Enhancing Neural Architecture Search with Multiple Hardware Constraints) are the strongest constraint-handling search methods in the file. ConNAS steers architecture gradients toward feasibility. DUCCIO uses hinge penalties with a scheduled weight to sidestep the problem of hand-tuning the penalty strength. Both search over dense operator and width choices and carry no accuracy-safety signal beyond the task loss. Our method replaces their gradient search with an exact discrete solve, and it adds a search dimension they lack: sparsity structure inside a layer.
SPARCS (Spectral Architecture Search for Neural Networks) is the closest work by name. It parameterizes connectivity through eigenvalues to grow or prune neurons. It has no hardware model and is shown mainly on multilayer perceptrons and classification heads, so it neither competes with nor supplies our method.
SparseNAS (Neural Architecture Search as Sparse Supernet) prunes supernet paths with group lasso. That makes it algebraically sparse but blind to both the spectrum and the device.
Research Program
The first component is a coarsened sparsifier. For each tile format, we compute block-level effective resistances on the coarsened bipartite graph. Because a single layer's graph has at most a few thousand super-nodes, these can be computed exactly. We sample with replacement until we reach a target density. We also record $\varepsilon_l$ for the result, measured directly on the original fine-grained Laplacian using a few dozen extreme generalized eigenvalues found by Lanczos iteration. The guarantee holds only for the coarsened graph. We treat the gap between the coarse and fine guarantees as an empirical quantity to report, not a solved problem.
The second component is a per-device sparse lookup table. Using the HW-NAS-Bench measurement pipeline, we time each layer shape under each configuration on two devices: a Raspberry Pi 4 with block-sparse and channel-pruned kernels, and a Jetson TX2 with dense, channel-pruned and block-sparse kernels. Each format is measured at roughly ten densities. We include the Edge TPU, which has no sparse support. There the only executable "tile" is a whole channel, and the method reduces to spectral channel selection. This lets us test whether the spectral signal helps even when hardware allows nothing finer.
The third component is the allocation solver described above. It takes the per-layer tables for distortion and latency and returns one configuration per layer. All candidate configurations are scored once with no training, so a full latency-accuracy curve costs one solve per budget value, followed by a single fine-tuning run for each chosen point.
Baselines
The naive reference point is uniform structured pruning. Every layer gets the same block format and the same density, with blocks chosen by magnitude, and the density is set so that measured latency meets the budget. This tells us how much is gained by allocating budget across layers at all.
The strongest pruning competitor is greedy structured saliency pruning under the same lookup table. Whole tiles are removed in order of SNIP, SynFlow or magnitude score, picking the tile with the best saliency-per-millisecond until the budget is met. This is what a practitioner would build, it uses the same hardware information we do, and Laenen found it fails at high sparsity only in the unstructured setting. Whether it also fails at tile granularity is the open question.
A further baseline is empirical sensitivity allocation. For every layer and configuration, we measure the actual drop in validation accuracy when only that layer is pruned. We then feed those drops into the same solver in place of $\varepsilon_l$. This isolates our key ingredient: it holds the hardware format, the lookup table and the exact solver fixed, and swaps only the spectral score for a directly measured one.
We also include Laenen's unstructured spectral sparsifier at the same parameter count, with latency measured on the device. This shows how much speed is lost by ignoring the hardware.
The architecture-search competitor is ConNAS run in the same latency budget. It produces dense, narrower networks searched over a channel-width space built around the same backbones, constrained by the same measured lookup table.
Every method gets the same pretrained weights, the same fine-tuning schedule, and the same number of fine-tuning epochs. Any method with a tunable knob gets the same number of tuning trials.
We have found no reported result on Lacuna for any of these methods measured as device latency versus accuracy on VGG or ResNet with block-sparse kernels. Laenen reports only a 61-second pruning time against 1,620 seconds for global sparsification, with no tabulated accuracies. The closest reported numbers come from ConNAS: it met the constraint in 100% of runs and came within 0.14–0.65% of the best constraint-satisfying accuracy on NATS-Bench with a Jetson TX2 budget. That is a different task, so all baselines will be re-run.
Beating the baselines means two things. First, at least a one-point accuracy gain over greedy saliency pruning and over sensitivity allocation, averaged over latency budgets at 3× speedup and beyond, with seed variance reported. Second, matching or exceeding ConNAS's dense networks at equal measured latency on at least one device.
Why not just…?
Why not just prune greedily by saliency under a latency table? At the granularity of single weights, Laenen shows greedy selection collapses layers and loses $\lambda_2$ at high sparsity, while spectral sampling does not. Coarse tiles may protect connectivity on their own, which would weaken our case. The greedy baseline, together with tracking $\lambda_2$ for both methods across density levels, decides this directly. If greedy matches us at tile granularity, we will report that spectral preservation only matters for fine patterns.
Why not just measure each layer's sensitivity empirically? This is a serious threat. Measured accuracy drops may simply be a better score than spectral distortion. The argument for the spectral score is that it is computed without evaluation passes, and that the layerwise theory justifies combining layers through a max. Empirical sensitivities, by contrast, are known to interact once several layers are pruned together. The sensitivity-allocation baseline holds everything else fixed. If it wins, the spectral contribution reduces to cheaper scoring, and we will say so.
Why not just search a narrower dense network with ConNAS or DUCCIO? On hardware with poor sparse-kernel support, such as the Edge TPU, dense narrow networks may dominate. HW-NAS-Bench's findings on how differently devices behave make this plausible. That is exactly why ConNAS at equal measured latency is a baseline, and why we report results per device rather than averaged. The useful outcome is a map of which devices and budgets favor structured spectral sparsity over width search.
Why not just use FLOPs instead of measured latency? HW-NAS-Bench's Kendall correlation of 0.18 between FLOPs and Edge TPU latency rules out FLOPs as a reliable proxy. We will additionally run the solver with a FLOP-count table in place of the latency table and report how far that allocation misses the latency budget on each device.
Proposed Experiments
We use VGG-16, ResNet-18 and ResNet-20 on CIFAR-10, CIFAR-100 and tinyImageNet, matching Laenen's setting. We prune at latency budgets between 1.5× and 6× speedup on the Raspberry Pi 4, the Jetson TX2 and the Edge TPU. The metrics are top-1 accuracy, measured latency, the rate at which the budget is actually met, and $\lambda_2$ before and after pruning.
As a transfer check, we apply the solver to architectures from the FBNet search space selected with HW-NAS-Bench lookup tables. This tests whether the method stacks on top of searched dense networks.
Three checks are decisive.
The first tests whether the sparse-kernel lookup tables stay additive: whole-network latency predicted by summing the tables should be within a few percent of measured latency. If it is not, the exact solver is invalid and must be replaced by measured refinement.
The second tests whether $\varepsilon_l$ predicts accuracy better than saliency mass. We will report the rank correlation between per-layer distortion and per-layer accuracy drop, compared against the same correlation for summed saliency.
The third is the accuracy comparison at equal latency against the sensitivity-allocation and ConNAS baselines. Its outcome determines whether the spectral ingredient adds anything beyond a good hardware table and an exact solver.
References
- One-Shot Neural Network Pruning via Spectral Graph Sparsification
- HW-NAS-Bench: Hardware-Aware Neural Architecture Search Benchmark
- Unifews: You Need Fewer Operations for Efficient Graph Neural Networks
- StructSAM: Structure- and Spectrum-Preserving Token Merging for Segment Anything Models
- Constraint-guided Hardware-aware NAS through Gradient Modification
- Enhancing Neural Architecture Search With Multiple Hardware Constraints for Deep Learning Model Deployment on Tiny IoT Devices
- Spectral Architecture Search for Neural Networks
- Neural Architecture Search as Sparse Supernet