Approximation theory and hardware profiling disagree about the shape of an efficient network. The theory says that a network kept very narrow can still represent almost anything if it is made deep enough. Profiling says the reverse: on a GPU or an edge accelerator, every extra layer costs a fixed amount of time to launch and synchronize, so deep, thin networks are the slowest way to spend a compute budget. Architecture search, the automated process of choosing a network's layer counts and widths, sits between the two and settles neither. Its width ranges are picked by hand, and the cost signals it uses, such as floating-point operation counts (FLOPs) or zero-cost proxy scores, are known to mislead it toward deep, thin designs.
This note proposes a single quantity that both sides can share: nonlinear depth, the number of sequential layers that cannot be merged into a neighbor after training. Chains of purely linear layers can be multiplied into one layer after training, so they cost latency only during training and add no expressive power. Nonlinear layers are what approximation theory trades against width, and they are also what fixes the sequential latency floor on hardware. Combined with a per-device saturation width, the channel count below which a layer's runtime stops shrinking because fixed overheads dominate, this gives a search space with two axes, each measurable in minutes on the target device. The search then looks only along a short frontier instead of over a combinatorial space.
Core Claim
On a given device, the latency of a feedforward vision network is predicted, in rank order, far better by a two-term model than by FLOPs. The first term charges a fixed cost per non-fusible layer. The second charges a roofline cost (whichever of compute time or memory-transfer time is larger) per layer:
$$ T(\text{net}) \approx D_{nl}\, c_{\text{dev}} + \sum_{l=1}^{D_{nl}} \max\!\left(\frac{F_l}{P_{\text{dev}}},\ \frac{B_l}{M_{\text{dev}}}\right), $$
Here $D_{nl}$ is nonlinear depth after fusing linear runs, $c_{\text{dev}}$ is the device's per-layer launch and synchronization cost, $F_l$ and $B_l$ are the FLOPs and bytes moved by fused layer $l$, and $P_{\text{dev}}$ and $M_{\text{dev}}$ are the device's sustained compute and memory throughput. The form comes from treating each fused layer as a separate kernel that cannot overlap with its successor. That is the sequential-execution argument behind ParNet's depth-over-frequency latency floor, with memory traffic added as in ShuffleNet V2. Setting the per-layer terms equal gives the saturation width $w^*_{\text{dev}}$. Below that width, a layer costs about $c_{\text{dev}}$ no matter how narrow it is, so narrowing it saves no time and only removes capacity.
The claim built on this model is that, on every device we test, the accuracy-latency frontier lies almost entirely inside a reduced space. In that space, widths are at least $w^*_{\text{dev}}$, the search variable is $D_{nl}$, and extra linear layers are used only as training-time over-parameterization. If so, the device-specific search problem shrinks to a few dozen candidates, and its width bounds come from measurement rather than from habit.
Where This Sits in Prior Work
The proposal reuses two methods.
The first is fusion. Double-Win NAS trains deep linear chains, multiplies them into one layer after training, and reports up to 1.9× speedup on Jetson Xavier with no ImageNet top-1 loss. It also finds that linear operations account for more than 93% of latency there. It treats fusion as a search trick. We treat the depth that remains after fusion as the search's primary coordinate.
The second is the nonlinear-capacity repair from VanillaNet. It merges consecutive 1×1 convolutions after training and compensates for the lost nonlinearity with a sum of shifted activations. We adopt that activation as one way to raise expressivity per nonlinear layer without adding sequential kernels.
Three lines of work motivate the gap.
The first is hardware profiling. The Efficiency Misnomer and Kedia et al. show that deep, narrow scaling is penalized by repeated kernel launches. Wide Residual Networks shows a 16-layer wide network matching a 1000-layer thin one. None of these turns the observation into a measured, per-device width floor.
The second is the misleading signals that search relies on. HW-NAS-Bench reports FLOPs-to-latency Kendall correlation as low as 0.18 on Edge TPU. It answers with tabulated measurements rather than a model that transfers to new devices.
The third is proxy bias. ZiCo-BC finds that zero-cost proxies drift toward deep, thin networks and corrects this with a tuned logarithmic penalty. That penalty has no hardware term. We test whether a measured saturation width removes the same bias without a tuned coefficient.
Approximation theory both constrains and informs the design.
Johnson shows that plain networks of width at most the input dimension cannot form closed decision boundaries. Lu et al., Kidger and Lyons, and Park et al. pin down critical widths near the input dimension. Lin and Jegelka show residual networks escape the floor even at width one, but only with depth that grows exponentially in dimension.
We do not use these width floors as pruning rules. For convolutional layers with dozens of channels they are almost never binding, and treating them as constraints, which is the obvious reading of the gap, would prune nothing. What we take from the theory is the observation that linear depth adds no expressive power while nonlinear depth substitutes for width. That observation lets us treat fused linear layers as free at inference time and treat $D_{nl}$ as the true exchange currency. Yu et al. add a caution: narrow networks can memorize the training set and still generalize badly. So we measure frontier quality on held-out accuracy, never on training fit.
Research Program
The work has three parts.
Device calibration. For each device we fit $c_{\text{dev}}$, $P_{\text{dev}}$ and $M_{\text{dev}}$ from a microbenchmark of single fused layers swept over width, about a hundred measurements per device. We read off $w^*_{\text{dev}}$ per stage resolution. The devices are those of HW-NAS-Bench (Jetson TX2, Raspberry Pi 4, Pixel 3, Edge TPU, the Eyeriss simulator and ZC706 FPGA), plus Jetson Xavier so we can compare against Double-Win NAS on its own hardware.
Expressivity exchange rate. Using the synthetic ring task of Johnson and the wide-target fitting task of Lu et al., we measure how much width replaces one nonlinear layer at fixed held-out error. We then check two predictions. Adding linear layers that will later be fused should never rescue a network below the topological floor. Adding nonlinear depth, residual or not, should rescue it. This tests whether $D_{nl}$, rather than total depth, is the right axis before we build the search on it.
Reduced search. We search over $D_{nl}$, stage widths at or above $w^*_{\text{dev}}$, and training-time linear expansion factor, with and without series activations. Because the reduced space is small, we evaluate it with short training runs instead of a supernet. That avoids the skip-connection collapse that NAS-Bench-201 documents for differentiable search.
Baselines
Naive reference. The do-nothing reference is FLOP-constrained search with hand-set width ranges, using FLOPs as the latency stand-in. On the latency-prediction side this is the 0.18 Kendall correlation on Edge TPU reported by HW-NAS-Bench. On ImageNet it is a manually scaled EfficientNet-style family, which ZiCo-BC reports as 11% slower on Galaxy S10 than its corrected search at equal accuracy. We count our latency model as beating this reference if its rank correlation exceeds FLOPs' on all six devices.
Lookup-table search. The strongest competitor on latency prediction is the measured latency table of HW-NAS-Bench, combined with random or evolutionary search. It is ground truth rather than a model. We run it with the same number of on-device measurements our calibration uses, and also with the full table. We beat it if our frontier matches its frontier at roughly a hundred measurements per device, against tens of thousands, and if our model ranks architectures correctly on a held-out device whose table we never consult.
Strongest ImageNet methods. The strongest end-to-end competitors are Double-Win NAS and TF-NAS. Double-Win NAS reports +0.8% ImageNet top-1 over FBNet-C with 1.3× speedup on Jetson Xavier. TF-NAS-A reports 76.9% top-1 within 0.06 ms of its latency target on a Titan RTX, at 1.8 GPU-days of search. We rerun both on Jetson Xavier and Raspberry Pi 4 with the same training recipe, epochs and search-plus-training GPU budget as ours. We beat them if our models sit strictly above their accuracy-latency curves at matched latency on at least one device, while not falling below on the others. VanillaNet-9 (79.87% at 2.91 ms on A100) serves as a reference point for the shallow plain-network regime on server GPUs.
Proxy-bias correction. ZiCo-BC is the baseline for the proxy-bias question. We run it in our space with its coefficient tuned on the same validation budget we use for our own choices.
Key ablations. Three ablations isolate the ingredients. The first keeps the width floor but searches total depth instead of $D_{nl}$. The second searches $D_{nl}$ with heuristic width ranges instead of $w^*_{\text{dev}}$. The third drops training-time linear expansion. The proposal's claim holds only if each of these loses frontier quality.
Why not just…?
Why not just use HW-NAS-Bench lookup tables with random search? On the 15,625-architecture NAS-Bench-201 space this is a real threat. Exhaustive lookup is cheap there, and random search is already competitive according to NAS-Bench-201. We expect to tie on that space and say so. The proposal's value has to show where tables do not exist: in larger spaces such as FBNet, and on a new device calibrated from a hundred measurements. The held-out-device test settles this. If tables plus random search, given the same small measurement budget, recover the frontier equally well, the latency model adds nothing and the contribution reduces to the width-floor observation.
Why not just fuse linear layers as Double-Win NAS does, and stop there? Fusion already removes linear depth, so Double-Win NAS plus heuristic widths may capture most of the gain. The ablation that searches $D_{nl}$ with heuristic widths measures exactly this. If it matches the full method, the saturation-width floor is unnecessary and we will report that. Our expectation of a gap rests on the observation in ShuffleNet V2 and HW-NAS-Bench that fixed overheads and memory traffic vary strongly by device. A single hand-set width range is unlikely to sit at the saturation point on both Edge TPU and Raspberry Pi.
Why not just correct proxy bias with ZiCo-BC? Its penalty works, reporting 29% lower latency on Galaxy S10 for detection, but it needs a tuned coefficient and contains no device information. In our space we will check whether the saturation-width floor removes the deep, thin drift on its own. If ZiCo-BC with tuning matches us, our method's advantage is only that it needs no tuning, which is a smaller claim.
Why not just prune and quantize a large network? Non-uniform channel pruning fragments tensors and raises memory traffic, which ShuffleNet V2 identifies as a reason fewer FLOPs often buy no GPU speedup. Our latency model also predicts that pruning cannot reduce $D_{nl}$, which on overhead-bound devices is the dominant term. We include magnitude-pruned ResNet-50 at matched latency as a check. If pruning reaches our frontier, the depth term is less important than claimed.
Why not just enforce the minimum-width theorems as search constraints? The proven floors are near the input dimension of a fully connected layer. For convolutional channel counts in real search spaces they almost never bind, so they would prune essentially nothing. We use the theory to justify treating linear depth as free and nonlinear depth as the exchange currency, not as a pruning rule.
Proposed Experiments and Decisive Checks
Latency-model check. We compute Kendall correlation between predicted and measured latency for all NAS-Bench-201 architectures on the six HW-NAS-Bench devices, defining $D_{nl}$ as the longest chain of convolutions through the stacked cells after fusing. We compare against FLOPs and against a table-trained neural predictor with the same measurement budget. The model fails if it does not clearly exceed FLOPs on Edge TPU and Raspberry Pi.
Frontier-retention check. Because NAS-Bench-201 is enumerable, we compute exactly what fraction of the measured accuracy-latency frontier for CIFAR-10, CIFAR-100 and ImageNet-16-120 survives the reduction to the $D_{nl}$-and-width-floor space. Its best architectures reach 94.37%, 73.51% and 47.31% respectively, per NAS-Bench-201. NAS-Bench-201 fixes channel widths, so on it only the $D_{nl}$ axis is tested. The width floor is tested in the FBNet space via HW-NAS-Bench latencies, together with short-schedule ImageNet training of the sampled candidates. Retaining under about 90% of frontier points would refute the core claim.
Synthetic exchange-rate check. On the ring task and the wide-target fitting task, we report held-out error as a function of width, nonlinear depth, and fusable linear depth. The key prediction is that fusable depth leaves the topological failure below the floor unchanged, while nonlinear depth does not. If fusable linear depth helps held-out error in these tasks beyond what optimization ease explains, the separation the method rests on is weaker than assumed.
End-to-end check. We report ImageNet top-1 against measured latency on Jetson Xavier and Raspberry Pi 4 versus Double-Win NAS, TF-NAS and ZiCo-BC at matched budgets, alongside the three ablations, and report COCO detection with the found backbones as a secondary transfer test. The decisive outcome is a frontier that strictly dominates on at least one device and is reached with a search cost below TF-NAS's 1.8 GPU-days. Otherwise nonlinear depth is a useful explanation but not a better search method.
References
- Non-deep Networks
- ShuffleNet V2: Practical Guidelines for Efficient CNN Architecture Design
- Double-Win NAS: Towards Deep-to-Shallow Transformable Neural Architecture Search for Intelligent Embedded Systems
- VanillaNet: the Power of Minimalism in Deep Learning
- The Efficiency Misnomer
- Transformers Get Stable: An End-to-End Signal Propagation Theory for Language Models
- Wide Residual Networks
- HW-NAS-Bench: Hardware-Aware Neural Architecture Search Benchmark
- ZiCo-BC: A Bias Corrected Zero-Shot NAS for Vision Tasks
- Deep, Skinny Neural Networks are not Universal Approximators
- The Expressive Power of Neural Networks: A View from the Width
- Universal Approximation with Deep Narrow Networks
- Achieve the Minimum Width of Neural Networks for Universal Approximation
- ResNet with one-neuron hidden layers is a Universal Approximator
- Generalizablity of Memorization Neural Network
- NAS-Bench-201: Extending the Scope of Reproducible Neural Architecture Search
- TF-NAS: Rethinking Three Search Freedoms of Latency-Constrained Differentiable Neural Architecture Search