Several of the fastest ways to choose a neural network architecture without training it rest on one idea. A ReLU network cuts its input space into many flat pieces, called linear regions, and a network that makes more cuts at random initialization is assumed to be more expressive and therefore better. These scores share a known failure: they mostly reward size. Bigger networks make more cuts, so the search drifts toward bloated models unless someone adds a hand-tuned parameter penalty. This note proposes to replace that penalty with one taken from tropical geometry, the algebra in which ReLU networks are maxima of affine functions. That algebra yields, for any given architecture, a computable ceiling on how many regions it could ever produce. We propose to score each candidate architecture by how much of its own ceiling it actually reaches at initialization, rather than by its raw region count. Raw counts are then measured exactly, not sampled, on two-dimensional slices of input space through real images. In two dimensions the tropical computations that are hopeless in high dimensions become cheap.
In short, the proposal computes a tropical upper bound on regions for each architecture, measures the realized regions exactly on a few planes through the data, and ranks architectures by the log of the ratio. The bet is that this ratio carries the useful structural signal in region-based proxies with the size signal removed. It also has a clear way to fail: if dividing by parameter count works just as well, the tropical machinery is not earning its keep, and we will say so.
Core Claim
A ReLU network is a tropical rational function, a difference of two convex piecewise-linear functions (Tropical Geometry of Deep Neural Networks). The maximal number of regions it can carve is governed by vertex counts of Minkowski sums of polytopes, and Sharp bounds for the number of regions of maxout networks and vertices of Minkowski sums gives exact shallow formulas and depth-wise product bounds. That paper notes that these are worst-case numbers and say nothing about networks at random initialization. Training-free search (Neural Architecture Search on ImageNet in Four GPU Hours, Neural Architecture Search without Training) lives entirely at initialization and has used only realized counts. Our claim is that the gap between the two quantities is the informative one.
For an architecture $a$ with random initial weights, let $R_a(P)$ be the exact number of linear regions of the network restricted to a two-dimensional affine plane $P$ through three training images. Let $B_a$ be the tropical upper bound on that number for $a$ with input dimension two. We score
$$ s(a) = \frac{1}{|\mathcal{P}|}\sum_{P \in \mathcal{P}} \log R_a(P) \;-\; \log B_a , $$
where $\mathcal{P}$ is a small set of such planes. Both terms grow with width and depth, so we expect size to largely cancel. What remains should reflect how skip connections, pooling, and zeroed edges cause realized cuts to coincide or collapse relative to what the operations could in principle produce. The prediction can be falsified. Among architectures of equal parameter count, $s(a)$ should correlate with trained accuracy. It should also have much lower partial correlation with parameter count than raw region proxies do.
Why the two-dimensional slice matters
The exact boundary-counting algorithm of Exact Count of Boundary Pieces of ReLU Classifiers tracks Minkowski sums of dual point sets layer by layer. Its authors could only run it on two-dimensional toy data, because vertex enumeration explodes with input dimension. We turn that restriction into the design. Composing the network with the affine map from $\mathbb{R}^2$ onto the plane $P$ gives a ReLU network with two inputs, whatever the image resolution. In the plane, Minkowski sums of polygons have size linear in their vertex counts. The planar subdivision can be built exactly by propagating affine pieces and splitting polygons along each neuron's zero line. The same pass counts the pieces of the decision boundary, meaning where the top-scoring class changes, so we get a boundary-piece count for free.
The bound $B_a$ is computed from the cell graph alone. A ReLU layer of width $w$ multiplies the region bound by at most $\sum_{j=0}^{2}\binom{w}{j}$, which is the hyperplane-arrangement count in two dimensions and the shallow case of the Montúfar formula. Addition of two branches is a Minkowski sum in the dual picture, so its bound is that of the common refinement. Average pooling and $1\times1$ convolutions are linear and do not add cuts by themselves. Batch normalization is frozen to its initialization statistics so that it is affine and the network stays piecewise linear. This is a modelling choice we will state and test against the batch-statistics variant. The exact-shallow, loose-deep character of the bound is a known weakness. We will measure directly whether its looseness varies systematically across operation types, because that would corrupt the ratio.
Research Program
The first step is engineering and validation. We will implement exact planar region and boundary-piece counting for NAS-Bench-201 cells, the 15,625-architecture cell space of NAS-Bench-201 whose operations (zero, skip, $1\times1$ conv, $3\times3$ conv, $3\times3$ average pool) are all piecewise linear under frozen normalization. We will check it against brute-force dense grid evaluation and against the 2D spiral and Gaussian-mixture settings of the exact-count paper. We will also report wall-clock cost per architecture, since the method is pointless if it is far slower than activation-pattern proxies that run in seconds.
The second step is the bound itself: a graph-propagation routine for $B_a$, plus an audit of how tight it is. For small cells we will compare $B_a$ with the largest region count found by optimizing weights to maximize regions on a plane. This tells us whether the denominator measures architecture or mostly measures bound slack.
The third step is the proxy study proper. We will evaluate $s(a)$, raw $\log R_a$, and the boundary-piece analogue on all of NAS-Bench-201 for CIFAR-10, CIFAR-100, and ImageNet-16-120. We will then move to NAS-Bench-101 and to the macro and micro spaces of TransNAS-Bench-101 through the NASLib harness of NAS-Bench-Suite-Zero, which also provides the competing proxies already implemented. A secondary question uses the boundary-piece count. Exact Count of Boundary Pieces of ReLU Classifiers found that adversarial training simplified boundaries (377 to 259 pieces on spirals) without losing accuracy, which suggests that rewarding cuts may favour fragile models. Raw region-maximizing search, as in TE-NAS, would worsen that. A ratio score need not.
Baselines
The naive reference points are parameter count and FLOPs used as rankers on their own. They matter because the whole claim is about separating structure from size. Any proxy whose rank correlation does not clearly exceed that of parameter count is mostly measuring size. They cost nothing and will be read off the benchmark tables.
The strongest existing competitor is the regularized SWAP score of SWAP-NAS. It counts distinct activation patterns per neuron across samples, which avoids the batch-size saturation of NASWOT, and it multiplies by a parameter-count regularizer. That makes it the hand-tuned version of exactly what our tropical denominator is supposed to do automatically. It reports a Spearman correlation of 0.90 with CIFAR-100 accuracy on NAS-Bench-201, against 0.80 for NWOT. We will rerun it in the same harness, on the same architectures, with the same number of input images. Because its regularizer has a tunable exponent, we will give it the same tuning budget we give our score, selected on one dataset and frozen for the others. Beating it means matching or exceeding its Spearman correlation on CIFAR-100 with no size hyperparameter. It also means a clearly lower correlation with parameter count, since matching 0.90 while carrying less size signal is the substantive win.
The direct linear-region predecessor is the region term of TE-NAS (Neural Architecture Search on ImageNet in Four GPU Hours), which estimates regions from activation transitions on sampled inputs. That paper reports 93.9% CIFAR-10 accuracy for its selected NAS-Bench-201 architecture, against an oracle of 94.37% reported by NAS-Bench-201. We will compare both its region term alone and its full combination with the NTK condition number, swapping our score in for the region term to see whether the joint search improves. NASWOT (Neural Architecture Search without Training) reports finding a 92.81% CIFAR-10 network in 30 seconds and is included as the fast activation-pattern reference. We will also include the data-free synflow proxy and the synflow, jacob_cov, and snip vote of Zero-Cost Proxies for Lightweight NAS, which reports a Spearman correlation of 0.82 for that vote. Zen-Score from Zen-NAS completes the set as the Gaussian-complexity alternative.
Three ablations isolate the key ingredient. The first replaces $\log B_a$ with $\log$ parameter count and with $\log$ FLOPs, tuned with a free coefficient. The second replaces exact planar counting with dense grid sampling on the same planes, and with TE-NAS-style sampling at matched compute. The third replaces data-anchored planes with planes through random Gaussian points. The proposal survives only if the tropical denominator beats the first ablation.
Why not just…?
Why not just divide an existing region or activation-pattern count by parameter count? This is the serious threat, and SWAP-NAS's regularizer is essentially this. Parameter count treats a $3\times3$ convolution and a skip connection as differing only in weights. The tropical bound treats them as differing in how many cuts they can add and how branches combine. If that distinction carries no information beyond size, the first ablation will match $s(a)$. In that case the honest conclusion is that tropical bounds explain the size bias but do not fix it better than a scalar penalty, and we would report it that way. The decisive measurement is the correlation with accuracy within bins of matched parameter count, where no size normalization can help.
Why not just sample regions densely instead of counting exactly? Dense grids on a plane may well approximate counts closely enough. Exactness then buys only lower variance, and possibly not lower cost. We test this head on with the grid-sampling ablation at matched wall-clock. If grids match, the method keeps the tropical denominator and drops exact counting. The exact routine remains necessary to validate the grid and to count boundary pieces, which thin grids systematically miss.
Why not just ensemble existing proxies in a learned surrogate? NAS-Bench-Suite-Zero shows that XGBoost surrogates over many proxies improve rank correlation by up to 42%. So a single new proxy has to justify itself as a feature, not only as a standalone ranker. We will add $s(a)$ to that surrogate and report the marginal gain at a fixed number of labelled architectures. A size-free feature should add information that size-dominated features cannot. If the gain is negligible, $s(a)$ is redundant with what the ensemble already captures.
Why not just use differentiable search such as GAEA? Geometry-Aware Gradient Algorithms for Neural Architecture Search reports 94.10% CIFAR-10 and 73.43% CIFAR-100 on NAS-Bench-201, near the oracle. It still trains a supernet. This proposal targets the regime of seconds per architecture with no weight updates, so GAEA marks the accuracy ceiling we compare against rather than a method we aim to replace.
Decisive Checks
Three results decide the project. On all three NAS-Bench-201 datasets, we will compare $s(a)$ to the parameter-count-normalized ablation in Spearman correlation within matched-parameter bins. Overall we will compare it to SWAP's 0.90 on CIFAR-100, with its partial correlation to parameter count reported next to each. The first comparison is the go/no-go test. We will also run the selected-architecture test, picking the top-scored cell from 1,000 random samples, repeated over seeds, and reporting its benchmark accuracy against TE-NAS's 93.9% and NASWOT's 92.81% on CIFAR-10 and against the 94.37% oracle. Finally, for transfer, the same frozen score goes to NAS-Bench-101 and TransNAS-Bench-101. Accuracy-correlation figures for SWAP on TransNAS-Bench-101 were not available in our sources (no reported result found on Lacuna for SWAP-NAS on TransNAS-Bench-101), so we will produce them ourselves. Smooth activations fall outside the method, because tropical representations need piecewise-linear operations, so search spaces using GELU or attention are explicitly excluded rather than approximated.
References
- Tropical Geometry of Deep Neural Networks
- Sharp Bounds for the Number of Regions of Maxout Networks and Vertices of Minkowski Sums
- Neural Architecture Search on ImageNet in Four GPU Hours: A Theoretically Inspired Perspective
- Neural Architecture Search without Training
- Exact Count of Boundary Pieces of ReLU Classifiers: Towards the Proper Complexity Measure for Classification
- NAS-Bench-201: Extending the Scope of Reproducible Neural Architecture Search
- NAS-Bench-Suite-Zero: Accelerating Research on Zero Cost Proxies
- SWAP-NAS: Sample-Wise Activation Patterns for Ultra-fast NAS
- Zero-Cost Proxies for Lightweight NAS
- Zen-NAS: A Zero-Shot NAS for High-Performance Image Recognition
- Geometry-Aware Gradient Algorithms for Neural Architecture Search