Budgeted Synaptic Rewiring of Operations for One-Pass Architecture Search

Architecture search usually costs far more than training the network it finds. Weight-sharing methods cut the search itself to GPU-days, but they still run every candidate operation on every step. They also tend to collapse onto parameter-free skip connections, and the winning architecture must then be retrained from scratch, where its ranking often fails to hold. Neuroscience offers a different model of how wiring gets chosen. In synaptic sampling, each connection carries a hidden variable that drifts under a learning signal and diffuses under noise. When that variable goes negative the connection disappears, and it can later grow back, so the circuit keeps sampling wiring diagrams instead of settling on one.

We propose to apply this rule to whole operations rather than single weights. Each candidate operation on each edge of a cell (a 3×3 convolution, a pooling layer, a skip connection) is treated as one "synapse" with a hidden variable. At any moment only a fixed budget of operations is active, and only those are computed and trained. When an operation's variable falls below zero it goes dormant and another is revived. When training ends, the currently active operations and their weights form the deployed network. Search and final training become the same run, and the run's cost is set by the budget, not by the size of the search space.

Core Claim

Budgeted stochastic rewiring at the level of operations can produce a trained, deployable network for roughly the cost of one training run of a network of that size. We expect the result to match two-stage methods that pay for search plus retraining when compared at equal total GPU hours. The work would be new in three ways. It is the first to carry rewiring dynamics from the weight level to the operation level. It keeps a hard compute budget during the entire search, where supernets evaluate every candidate. And it tests directly whether the noise term matters, or whether a deterministic prune-and-regrow rule does the same job.

Mechanism and Its Lineage

The method comes from two sources. Synaptic Sampling shows that noisy dynamics on a hidden parameter $\theta$ sample from a posterior over both weights and wiring. Here the weight is zero whenever $\theta \le 0$, so pruning and regrowth fall out of one rule. Deep Rewiring turned this into a practical method for sparse deep networks with a strict connection budget $K$: whenever a connection goes dormant, a random dormant one is revived. It reports 96.3% on MNIST at 1% connectivity and 84.1% on CIFAR-10 at 5% connectivity. Both methods operate only on scalar weights inside a fixed architecture. Neither chooses between kinds of operation.

We keep their update rule but attach $\theta_{e,o}$ to operation $o$ on edge $e$:

$$\mathrm{d}\theta_{e,o} = \beta\left(\frac{\partial \log p(\theta)}{\partial \theta_{e,o}} + \frac{\partial \log p(\mathcal{D}\mid \theta, w)}{\partial \theta_{e,o}}\right)\mathrm{d}t + \sqrt{2\beta T}\,\mathrm{d}W.$$

In this rule, $\beta$ is a step size and $p(\theta)$ is a prior that charges each operation for its cost in FLOPs. The likelihood term $p(\mathcal{D}\mid\theta,w)$ scores how well the network explains the data given the operation weights $w$. $T$ is a temperature, and $\mathrm{d}W$ is Gaussian noise. An active operation contributes $\mathrm{softplus}$-scaled $\theta_{e,o}$ times its output. A dormant operation is neither computed nor updated; its weights are frozen until it is revived.

The central open design question is how a dormant operation earns its way back. Deep Rewiring revives connections uniformly at random. Gradient Rewiring argues that random revival wastes samples. It instead defines a stand-in gradient that estimates how the loss would change if a dead connection were switched on, and reaches 92.03% on CIFAR-10 at about 5% connectivity in spiking networks. It does so, however, by dropping the noise and with it the sampling interpretation. At the operation level, a stand-in gradient requires actually computing the dormant operation's output. That puts back the full-supernet cost we want to avoid.

We resolve this with a cost knob. Every $m$ steps, one small minibatch is run through all dormant operations to estimate their stand-in gradients. Between these probes, dormant variables move only by prior drift and noise. Setting $m=\infty$ recovers pure random revival. Setting $m=1$ gives full directed regrowth at supernet cost.

Research Program

We will build the rule in two budget modes. In the per-edge mode exactly one operation is active on each edge, so every visited architecture lies inside NAS-Bench-201. This allows every sampled architecture to be looked up in the benchmark's table of standalone accuracies. In the global mode, a total FLOPs budget is shared across all edges, so an edge may hold zero, one, or several operations. This mode goes beyond what categorical per-edge samplers can represent.

The analysis has three parts. First, we will trace how often the trajectory visits skip-heavy cells. BaLeNAS and NoisyDARTS tie skip collapse to sharp curvature and to an unfair early advantage for identity paths, and we want to know whether a hard budget with a FLOPs-priced prior prevents that. Second, we will measure how well the method's ranking of architectures matches the table's ranking. Third, we will sweep the temperature and the probe interval $m$ to map accuracy against compute.

One risk needs explicit handling. A revived operation returns with stale weights while its rivals kept training, and skip connections have no weights to go stale. Revival could therefore favor skips, reproducing the collapse in a new form. We will test a short grace period after revival, during which an operation cannot be pruned, and we will charge skip connections a small nonzero price in the prior.

Baselines

The naive reference point is random search: sample architectures from NAS-Bench-201, look up their accuracy, and keep the best. NAS-Bench-201 found that random search beat DARTS in this space. Outside the table, however, random search must pay to train every architecture it considers. We will run it with the same number of table queries our method visits, and separately at equal real training compute, where each candidate is actually trained. The benchmark's best achievable test accuracies are 94.37% on CIFAR-10, 73.51% on CIFAR-100, and 47.31% on ImageNet-16-120.

The strongest competitor on NAS-Bench-201 is BaLeNAS-TF from BaLeNAS. It learns a Gaussian distribution over DARTS routing weights and ranks sampled candidates with a training-free score. It reports 94.33% on CIFAR-10 and 46.54% on ImageNet-16-120. It is the closest existing method because it is also a Bayesian, sampling-based search that avoids collapse. It differs in running the full supernet with point-estimate weights and in retraining at the end. We will rerun it in our codebase with the same seeds and the same hyperparameter-tuning budget, and report its total cost including retraining. Beating it means one of two outcomes. We either match 94.33% on CIFAR-10 in table lookup while spending less total GPU time, or we exceed its accuracy at equal total time. The comparison also counts our in-run weights, which BaLeNAS cannot deploy directly.

For the single-stage question, the reference is DSNAS. It samples one operation per edge and trains the result for deployment without retraining. It reports 74.4% ImageNet top-1 at 330M FLOPs for 420 GPU hours in total. We will compare against those published figures under the same FLOPs limit.

For deterministic sparse search, the reference is SparseNAS, which reports 2.69% CIFAR-10 error for 0.25 to 1 GPU day and 24.67% ImageNet mobile top-1 error.

Two ablations isolate what matters. Setting the temperature to zero while keeping the probes tests whether noise contributes at all. Setting $m=\infty$ tests whether directed regrowth is worth its probe cost. A third ablation removes rewiring entirely and applies Deep Rewiring at the weight level to a fixed, hand-picked NAS-Bench-201 cell at matched parameter count. It tests whether operation-level search adds anything beyond weight-level sparsity.

Why not just…?

Why not just use NoisyDARTS with a well-tuned noise level? NoisyDARTS reaches 97.63% on CIFAR-10, a strong result. It still computes every candidate operation and retrains the winner, and its authors report that the noise variance is difficult to tune. Our claim concerns total cost, not collapse avoidance alone. If NoisyDARTS plus retraining matches our accuracy at equal total GPU hours, the budget argument fails, and the equal-compute comparison will show whether it does.

Why not just use DSNAS, which is already single-stage? This is the most serious threat. DSNAS already avoids retraining and computes only sampled paths. The differences are that it forces exactly one operation per edge and draws a fresh categorical sample on every step, with no persistent dormant state. In the per-edge mode our method is close to DSNAS with different exploration dynamics. We therefore expect gains, if any, mainly in the global-budget mode, and we will report the per-edge comparison even if it comes out a tie.

Why not just prune deterministically, as SparseNAS does? SparseNAS is cheap. Once its proximal step zeroes a path, however, that path cannot return. The zero-temperature ablation with probes is effectively deterministic prune-and-regrow. If it matches the noisy version, we will drop the sampling claim and present the method as budgeted operation-level regrowth.

Why not just rank architectures with zero-cost proxies? NAS-Bench-Suite-Zero shows that single proxies are biased toward large models, and proxies produce no trained weights. We include the proxy ensemble reported there as a pre-screen baseline at equal compute.

Decisive Checks

On NAS-Bench-201 across CIFAR-10, CIFAR-100, and ImageNet-16-120, we will report four quantities: the table-lookup accuracy of the final architecture, the in-run accuracy with no retraining, the gap between those two, and total GPU hours. The in-run to table gap directly measures the retraining gap that DSNAS identified.

In the DARTS CIFAR-10 space and the ImageNet 330M-FLOPs setting, we will plot accuracy against total GPU hours alongside the published points for BaLeNAS (2.37% error at 0.6 GPU days, before retraining), SparseNAS, and DSNAS.

The idea succeeds if it sits on or above that accuracy-versus-cost frontier and if the temperature-zero ablation is measurably worse. It fails if skip-dominated cells reappear despite the budget, or if a DSNAS-style categorical sampler matches it in the global-budget mode.