How Fast Can This Network Learn? A Kronecker-Factored Fisher Spectrum Score for Training-Free Architecture Search

Neural architecture search is expensive because judging a candidate design normally means training it. "Zero-cost proxies" avoid this by scoring each untrained network from one batch of gradients. In practice the popular scores mostly reward size: bigger networks get bigger gradient norms. We propose a score that asks a different question. Given the curvature of the untrained network, how much of the network can gradient descent actually train at a learning rate that does not diverge? The curvature comes from the Fisher information matrix, the matrix describing how sensitive the network's predictions are to each direction of parameter change. It is far too large to store, but its layer-wise Kronecker-factored approximation (K-FAC) splits each layer's Fisher into a small forward matrix (input-activation covariance) and a small backward matrix (gradient covariance). From the largest eigenvalue and the trace of these small matrices we can compute, in about the time of a few backward passes, the fraction of curvature that sits close to the stiffest direction. Because this is a ratio, it is roughly independent of parameter count by construction.

Put in two sentences: plain SGD can only use a learning rate about as small as the inverse of the sharpest curvature direction, so a network whose curvature is spread very unevenly trains slowly along almost every direction. We measure that unevenness cheaply at initialization using Kronecker-factored Fisher statistics, and test whether it ranks architectures better than existing proxies once model size is controlled for.

Core Claim

Let $\hat F$ be the block-diagonal K-FAC Fisher of a network at initialization. Its block for layer $l$ is $A_l \otimes G_l$, where $A_l$ is the input-activation covariance and $G_l$ is the pre-activation gradient covariance. Its eigenvalues are the products $a_i g_j$ of the factor eigenvalues. The proposed score is

$$ S = \frac{\operatorname{Tr}(\hat F)}{D \, \lambda_{\max}(\hat F)} = \frac{\sum_l \operatorname{Tr}(A_l)\operatorname{Tr}(G_l)}{D \, \max_l \lambda_{\max}(A_l)\lambda_{\max}(G_l)}, $$

with $D$ the parameter count. The form comes from a quadratic model of the loss. Gradient descent is stable only up to step size $2/\lambda_{\max}$, and at that step size the error along an eigendirection with curvature $\lambda_i$ shrinks at a rate proportional to $\lambda_i/\lambda_{\max}$. So $S$ is the average per-direction training speed at the largest stable learning rate. Computing it needs only traces and one power iteration per small factor matrix. The full $D \times D$ matrix is never formed, and no layer-sized matrix is inverted.

The claim is falsifiable. After partialling out log parameter count, $S$ should correlate with final accuracy on tabular benchmarks better than the existing gradient-based proxies. It should also beat the same statistic computed from a diagonal Fisher, which would show that the Kronecker structure, and not the ratio form alone, carries the signal.

Relation to Prior Work

The closest existing work is the "fisher" proxy in Zero-Cost Proxies for Lightweight NAS. That paper scores networks by a channel-collapsed sum of squared gradient-times-weight terms borrowed from pruning, alongside grad_norm, snip, grasp, synflow and jacob_cov, and shows that a vote of three proxies reaches 0.82 Spearman on NAS-Bench-201. Their Fisher score is diagonal and additive, so it grows with network size. Ours is spectral and normalized.

NAS-Bench-Suite-Zero standardizes 13 proxies over 28 tasks and documents their size bias. It contains no structured Fisher factorization. This motivates the proposal by establishing the gap, and it supplies the evaluation harness.

Two papers use structured Fisher for NAS but in a different place. IS-DARTS uses Fisher information of feature maps to prune operations progressively, with retraining between stages (2.0 GPU hours on NAS-Bench-201). Adaptive Stochastic Natural Gradient Method for One-Shot Neural Architecture Search and BaLeNAS apply natural gradients only to the distribution over architectures, and both still train a supernet. We do neither. We use the weight-space Fisher of each candidate, without training, as a predictor.

The method comes from the Kronecker line of work. We reuse the convolutional K-FAC construction of A Kronecker-factored approximate Fisher matrix for convolution layers. For a reference against the exact Fisher spectrum, we borrow the matrix-free Lanczos approach of Scalable Kronecker-Factored Fisher Approximation for Neural Network Parameter Sensitivity, which showed that non-diagonal Fisher structure can be extracted in seconds and that diagonal approximations miss sensitivity that matters.

That same paper also constrains us. Its optimality arguments assume a near-stationary point, and at initialization that assumption is badly violated. We therefore do not interpret $S$ as a Hessian surrogate. We motivate it only through the stability of gradient descent, and we measure empirically how its predictive value changes as the network takes its first training steps.

Understanding and Robustifying Differentiable Architecture Search motivates the focus on the top eigenvalue. It showed that a spike in the dominant Hessian eigenvalue predicts failed architectures in DARTS. That signal concerns architecture parameters during search. Ours concerns weight-space curvature of a single candidate before any training.

Research Program

The first component is a reusable estimator. For each layer it collects $A_l$ and $G_l$ from one or a few minibatches and reports traces and top eigenvalues by power iteration.

The labels used for the backward pass matter. We use the true Fisher, with labels sampled from the model's own predictions. At initialization the softmax output is close to uniform, so the empirical Fisher (built with dataset labels) and the true Fisher can differ substantially, and we report both.

The second component is a diagnostic study on small NAS-Bench-201 networks, where the exact Fisher's top eigenvalue and trace can be computed with Fisher-vector products and Lanczos. On these networks we quantify how far the Kronecker score departs from the exact score. We also measure how much the block-diagonal assumption, which ignores curvature between layers, distorts $\lambda_{\max}$.

The third component is a cost-versus-fidelity curve. We recompute $S$ after 0, 10, 100 and 1000 training steps. This tells us whether a few steps of training repair the stationary-point mismatch cheaply enough to beat reduced-training estimators of the kind studied in Rethinking Performance Estimation in Neural Architecture Search.

Baselines

The naive reference points are parameter count and FLOPs used directly as scores. Suite-Zero shows that many proxies largely track these. Any proxy that cannot beat log parameter count in raw Spearman correlation, and in correlation within parameter-count bins, has not demonstrated anything. These baselines cost nothing, so no tuning applies.

The strongest training-free competitor is the synflow, jacob_cov and snip vote from Zero-Cost Proxies for Lightweight NAS. It reports a Spearman correlation of 0.82 on NAS-Bench-201, and the same paper reports 0.61 for the reduced-training EcoNAS baseline. We rerun the vote ourselves through the Suite-Zero code paths. It gets the same architectures, the same single batch and seed protocol, and the same initialization.

$S$ alone beating 0.82 would be a strong result. The more realistic bar is this: $S$ matches the best single proxy in raw correlation, beats every single proxy in size-partialled correlation, and raises the vote when added as a fourth member.

The strongest learned competitor is the Suite-Zero surrogate, a gradient-boosted predictor that takes proxy features as input. The file reports gains of up to 42% in rank correlation for this surrogate but gives no absolute value that I can attribute to a specific space, so no reported result was found on Lacuna for its absolute Spearman. We train it with and without $S$ as an extra feature, using the same training-set sizes and hyperparameter search budget. The test is whether $S$ adds information beyond the 13 existing proxies.

Two ablations isolate the key ingredient. The first is the diagonal ablation: the same trace-over-$D\lambda_{\max}$ ratio computed from a diagonal Fisher. The second is the factor ablation: scores built from $A_l$ alone and from $G_l$ alone. The $A_l$-only score is close in spirit to activation-based proxies such as jacob_cov. If the full score does not beat both factor-only scores, the gradient side contributes nothing, and the proposal reduces to an existing proxy.

For search-level comparisons on the DARTS space, the references are Zero-Cost Proxies Meet Differentiable Architecture Search, which reports 24.4% ImageNet top-1 error after 25 minutes of search on one GPU, and IS-DARTS, which reports 2.56% CIFAR-10 error and 24.1% ImageNet error. On NAS-Bench-201 the ceiling is the 94.37% CIFAR-10 optimum reported in NAS-Bench-201, and IS-DARTS reaches 94.36% at 2.0 GPU hours. Beating these would mean matching their accuracy at a fraction of that search time.

Why not just…?

Why not just use parameter count, or rely on synflow and other existing proxies? Size is a real threat. It may be most of what any initialization score captures on benchmarks where bigger cells win. That is why size-partialled and within-bin correlations are our primary metric and not a secondary one. If $S$ adds nothing once size is controlled for, the claim fails, and we will report that outcome.

Why not just use the diagonal Fisher with the same ratio? It is cheaper, and the ratio form may be what does the work. Scalable Kronecker-Factored Fisher Approximation for Neural Network Parameter Sensitivity found that diagonal Fisher misses correlations that matter for compression. Compression is not ranking, however, so this is evidence and not proof. The diagonal ablation, together with the exact-Lanczos comparison on small networks, settles the question directly.

Why not just train each candidate briefly and rank by early accuracy? Reduced training reached only 0.61 Spearman at roughly a thousand times the compute in Abdelfattah et al. Brief training does help with the stationary-point mismatch, though. Our cost-versus-fidelity curve compares $S$ after $k$ steps against early accuracy after the same $k$ steps. If early accuracy dominates at every budget, the curvature score has no reason to exist.

Why not just ensemble existing proxies in a surrogate? The Suite-Zero surrogate may beat $S$ in absolute terms. We expect that, and we do not claim otherwise. The test that matters is whether $S$ improves the surrogate as an added feature.

Proposed Experiments

The primary study scores all 15,625 NAS-Bench-201 architectures on CIFAR-10, CIFAR-100 and ImageNet-16-120, plus the NAS-Bench-101 and NAS-Bench-301 subsets distributed with Suite-Zero. For each, we report Spearman and Kendall correlation with final accuracy, partial correlation controlling for log parameters, and correlation within parameter quintiles. Each score is computed over five seeds and three batch sizes. We report wall-clock time per architecture against synflow, since Zero-Cost Proxies for Lightweight NAS warns that FLOP savings often fail to translate into GPU time.

The decisive check has two conditions. In size-partialled correlation, $S$ must beat both the diagonal ablation and the best single proxy on at least two of the three NAS-Bench-201 datasets. And it must raise the Suite-Zero surrogate's correlation as an added feature.

A secondary search experiment uses $S$ in two places. On NAS-Bench-101 and NAS-Bench-201 it serves as the warm-up and move filter in aging evolution, following Abdelfattah et al.'s protocol at matched query budgets. On the DARTS space it replaces the perturbation score in Zero-Cost-PT, which gives a direct test against the 24.4% ImageNet error at matched search time.

The diagnostic experiments report three gaps on small networks: Kronecker versus exact Fisher, true versus empirical labels, and block-diagonal versus full $\lambda_{\max}$. Together they tell us which approximation, if any, the ranking signal actually depends on.