Scoring Architectures at the Lazy-Regime Transition

Neural architecture search, the automated search for a good network design, is expensive because every candidate has to be trained before it can be judged. "Zero-cost proxies" try to skip that training. They score each untrained network from one batch of gradients, and they borrow their formulas from pruning-at-initialization methods. These proxies have a documented blind spot. At initialization, a network whose gradients are exploding looks the same to them as a network that can learn quickly. Proxies such as snip and fisher therefore rank designs without skip connections far too high, and many proxies do no better than counting parameters (Evaluating Efficient Performance Estimators of Neural Architectures). The pruning community met the same problem and found two answers. One is to prefer criteria that preserve stable gradient flow over criteria that inflate it. The other is to wait a little before deciding: let training run until the network enters the "lazy kernel regime", the point where its linearized learning dynamics stop changing quickly, and prune then rather than at step zero (Winning the Lottery Ahead of Time).

This note proposes carrying that second lesson into architecture search. Each candidate is trained alone for a few dozen to a few hundred steps, and training stops when a cheap detector says the candidate has entered the lazy regime. At that moment we record how much the network's gradient flow and its neural tangent kernel have changed. The neural tangent kernel describes how a small weight update moves the network's predictions. The core bet is that an exploding network shows a large gradient norm at step zero followed by fast collapse and large kernel drift, while a network that genuinely trains well keeps its kernel stable. A short measured trajectory should separate these two cases where a single snapshot cannot. This proposal succeeds only if such a trajectory score beats the obvious competitor, plain validation loss after the same number of steps. The experiments are built around that comparison.

Core Claim

Gradient-based zero-cost proxies fail in a specific way: at $t=0$ they confuse large gradients with good trainability. That confusion can be removed by measuring the proxy at the onset of the lazy regime, detected separately for each architecture. The same holds for its change between initialization and that onset. This keeps the cost at a small, adaptive number of steps. The claim is about standalone short training. It does not contradict the finding of White et al. that proxies degrade on partially trained supernets, where many architectures share one set of weights. That degradation is plausibly caused by weights adapting jointly across many architectures, a condition we avoid and will test directly.

Research Program

The method has four pieces, and three of them are taken from existing pruning work. For each candidate we train with standard SGD and track the relative change in weight norm. Onset $t^*$ is declared when this change falls below a threshold, following the detector in EarlyCroP. We estimate the kernel trace as the squared Frobenius norm of the network Jacobian, averaged over fresh random weight draws and Gaussian-noise inputs. This is the inexpensive estimate of NTK-SAP, which showed it tracks the kernel spectrum well enough to guide pruning. We use it at two points in time, whereas NTK-SAP used it for one fixed backbone. The third piece concerns which quantity to measure. Lubana and Dick showed that inflating the gradient norm destroys capacity, while preserving it keeps capacity intact. Their preserving variant held about 68% accuracy where GraSP fell to 1%. We therefore score stability of gradient flow rather than its size. The score is

$$ S = \log \mathrm{tr}\,\Theta_{t^*} \;-\; \lambda \left| \log \frac{\mathrm{tr}\,\Theta_{t^*}}{\mathrm{tr}\,\Theta_{0}} \right| \;-\; \mu \left| \log \frac{g_{t^*}}{g_0} \right|. $$

Here $\Theta_t$ is the estimated kernel at step $t$ and $g_t$ is the gradient norm. The first term rewards capacity that remains at onset. The other two penalize drift in the kernel and in the gradient norm. The weights $\lambda$ and $\mu$ are fitted once on NAS-Bench-201 CIFAR-10 and then frozen for every other space. The onset time $t^*$ is logged as a separate feature, since how long a network takes to settle may itself carry information.

The fourth piece is the analysis that makes this a study and not just a new score. Using the 15,625 fully trained architectures in NAS-Bench-201, we will sort architectures by whether they have skip connections and by whether their initial gradient norm is anomalously large. We then check whether $S$ removes the overestimation of skip-free cells that snip and fisher show. This tests the mechanism directly rather than relying only on aggregate correlation.

The work will be implemented in NASLib. This gives access to the 13 proxies standardized by NAS-Bench-Suite-Zero, so every baseline runs through the same pipeline.

Baselines

The naive reference points are parameter count and FLOPs. They cost nothing, and they are the bar that White et al. found many proxies fail to clear. Any proposed score must beat them on Spearman and Kendall rank correlation in every space. We will also report results within groups of similar size, where size cannot help.

The strongest training-free baseline with a reported figure is the voting ensemble of synflow, jacob_cov and snip from Zero-Cost Proxies for Lightweight NAS. It reports a Spearman correlation of 0.82 on NAS-Bench-201, against 0.61 for the reduced-training baseline EcoNAS. Beating this ensemble means exceeding 0.82 on the same NAS-Bench-201 split, and we will rerun it in our own pipeline to confirm the number. The stronger learned version is the XGBoost surrogate over all 13 proxies from NAS-Bench-Suite-Zero. That paper reports gains of up to 42% in rank correlation over single proxies, given only as a relative figure. We will train this surrogate with and without our features added, using the same number of labeled architectures. The theory-based competitor is TEG-NAS (Chen et al.), which scores trainability by the kernel condition number at $t=0$. I found no reported Spearman correlation for TEG-NAS on Lacuna, so we will compute it ourselves.

The most dangerous baseline is matched-compute truncated training. Each architecture is trained for exactly $t^*$ steps, and also for a step count fixed at the dataset median, and is then ranked by validation loss or accuracy. Our score wins only if it beats this baseline at equal wall-clock cost per architecture, including the overhead Abdelfattah et al. call the "GPU gap".

Three ablations isolate the ingredients. The first computes the same $S$ features at $t=0$ only, which isolates the effect of waiting. The second replaces the adaptive $t^*$ with a fixed step count, which isolates the onset detector. The third swaps the stability-based score for raw gradient norm at $t^*$, which isolates the preservation-versus-inflation distinction.

Why not just…?

Why not just use parameter count or FLOPs? In NAS-Bench-201 every cell sits inside a fixed outer skeleton, so size varies little, yet CIFAR-10 accuracy spans up to the 94.37% optimum (NAS-Bench-201). Size cannot tell topologies apart there. On non-topological spaces such as NDS ResNet, however, size-like signals do well, and synflow was best there (White et al.). We expect a smaller advantage on those spaces and will report it rather than hide it.

Why not just train a few steps and read off validation loss? This is the real threat. Our method already pays for short training, and losses measured at the same moment might rank architectures just as well. Two things argue against it. Reduced training ranks poorly (EcoNAS reaches 0.61), and early losses barely separate before the lazy regime. Neither argument settles the question. The matched-compute baseline above does. If loss at $t^*$ ranks as well as $S$, we will say the kernel measurements add nothing and reframe the contribution as an onset-timed truncated-training rule. If the two are complementary, the surrogate experiment will show it.

Why not just debias snip for model size, or rely on the kernel condition number? Size-debiasing (NAS-Bench-Suite-Zero) addresses the bias toward large models, but not the confusion between exploding gradients and fast learning. A large gradient caused by explosion is not a size effect. The condition number in TEG-NAS does target trainability. It is still a $t=0$ measurement and requires the full kernel matrix. The grouped analysis by skip connections and gradient anomaly will show whether either one already removes the bias.

Why not just fix the supernet, as DARTS- does? DARTS- removes the unfair gradient-flow advantage of skip connections by adding an auxiliary skip path that decays to zero during search. It reaches near-optimal NAS-Bench-201 architectures. That is a fix inside one-shot search with shared weights. Our score ranks independent architectures and can serve random search or evolutionary search. We compare the two at the level of final architecture quality, not ranking quality.

Proposed Experiments

Ranking quality will be measured on NAS-Bench-201 (CIFAR-10, CIFAR-100, ImageNet-16-120) and on NAS-Bench-101. We will also use the 11,000-model evaluated subset of NAS-Bench-301 and the TransNAS-Bench-101 tasks available through NAS-Bench-Suite-Zero. Metrics are Spearman and Kendall correlation, top-1% recall, [email protected]% as defined by White et al., and measured GPU-seconds per architecture.

Search quality will be measured by plugging $S$ into random search and aging evolution as a warm-up filter, in the way Abdelfattah et al. used zero-cost proxies. We report the test accuracy reached against the NAS-Bench-201 optima of 94.37%, 73.51% and 47.31% at fixed search budgets, with DARTS- as a reference.

To address the White et al. contradiction directly, we will apply $S$ to weights taken from a partially trained NAS-Bench-201 supernet. We predict that ranking degrades there but not under standalone short training. This would locate the degradation in weight sharing rather than in training time.

The outcome that decides the proposal has three parts. $S$ must exceed 0.82 Spearman on NAS-Bench-201 CIFAR-10. It must beat validation loss at matched compute in at least three of the four spaces. It must remove the overestimation of skip-free cells in the grouped analysis. If $S$ passes the first part but fails the second, the kernel-measurement idea is refuted.