Ranking Architectures by the Features They Learn Early: Cheap Architecture Search for Worst-Group Robustness

Neural networks trained to minimize average error often learn shortcuts. A bird classifier decides "waterbird" from the water behind the bird instead of the bird itself, and it fails on the rare images where the two disagree. Architecture search, the automated design of network wiring, could in principle find networks that resist such shortcuts. The tools that make search affordable, however, were built to predict ordinary accuracy. One family is zero-cost proxies: scores computed from a single minibatch at random initialization. The other is low-fidelity proxies: scores from short or reduced training. On distribution shift these tools have already been shown to fail. We propose a different cheap score. Train each candidate briefly, discard its final layer, refit a linear classifier on a small group-balanced set, and rank the candidate by the worst-group accuracy of that refit.

The rationale comes from one finding in the spurious-correlation literature. On Feature Learning in the Presence of Spurious Correlations shows that ordinarily trained networks already encode the true object features. Most of the damage sits in the final linear layer, which over-weights the shortcut. If that holds during search, then an architecture's eventual robustness depends on how well its features separate the true signal from the shortcut. Both its early in-distribution accuracy and its untrained gradient statistics are confounded by the shortcut. Feature separability may also be readable long before training ends. The note tests whether this score ranks architectures for worst-group accuracy cheaply. It targets the regime where architecture actually matters: small networks trained from scratch without large-scale pre-training.

Core Claim

Our central hypothesis concerns what a cheap score must measure. To rank architectures by worst-group accuracy, it should measure the linear decodability of core features after a short run of standard training, not the trained model's own predictions and not initialization statistics.

Concretely, let $a$ be a candidate architecture. Let $\phi_a^{(t)}$ be its feature extractor after $t$ steps of ordinary training on the full biased training set. Let $\mathrm{WGA}(\cdot)$ denote accuracy on the worst-performing group, where a group is a combination of label and spurious attribute such as "waterbird on land." The proxy is

$$ S(a,t) = \mathrm{WGA}\big(\hat w_a \circ \phi_a^{(t)}\big), \qquad \hat w_a = \arg\min_w \; \mathcal{L}_{\text{bal}}\big(w \circ \phi_a^{(t)}\big), $$

where $\mathcal{L}_{\text{bal}}$ is logistic loss on a small group-balanced held-out set. It is evaluated on a separate group-annotated validation split.

The claim has three parts:

  1. $S(a,t)$ at a small $t$, about 5–10% of a full run, ranks architectures by their fully trained worst-group accuracy far better than the existing alternatives. Those alternatives are zero-cost proxies, parameter count, and short-training in-distribution accuracy.
  2. The final-layer refit is the ingredient that makes it work.
  3. A variant without group labels, which replaces true groups with groups inferred from the errors of a deliberately biased model, keeps most of the ranking quality.

Why the obvious ideas are not enough

The closest existing work maps the gap but does not close it. NAS-OoD searches cell-based convolutional networks against an adversarial image generator. It reaches 85.16% average accuracy on NICO with 3.1–3.5M-parameter networks that favour dilated convolutions. Its search couples three training processes and is expensive and unstable. It never reports worst-group accuracy on Waterbirds or CelebA, so it motivates the question but supplies no cheap method.

Vision Transformer Neural Architecture Search for Out-of-Distribution Generalization evaluates nine training-free proxies over 3,000 transformer sub-networks on ImageNet corruption and style shifts. It finds them worse than parameter count or compute. That is a constraining result: it tells us not to expect a generic initialization score to work.

Zero-cost Proxy for Adversarial Robustness Evaluation builds a robustness score at initialization from a kernel eigenvalue and input-curvature estimate. It reaches Kendall's τ of 0.33 on 223 adversarially trained models. Its target, small worst-case pixel perturbations, is a different failure from semantic shortcuts. It also shows a systematic bias against skip connections.

The obvious move would be "a zero-cost proxy for spurious correlations." One natural form is a Fishr-style difference in per-group gradient variances computed at initialization. Fishr matches such variances during training as a regularizer. We include this as a baseline rather than our method, because there is a principled reason to doubt it. Shortcut reliance is a property of training dynamics. Overparameterization hurts worst-group accuracy with spurious correlations describes networks that use the cleaner spurious cue for majority examples and memorize the minority. That behaviour does not exist at random weights. At initialization, gradient variance differences across groups mostly reflect input statistics.

The other obvious move is low-fidelity search using in-distribution validation accuracy, as in Rethinking Performance Estimation in Neural Architecture Search. It runs straight into ID and OOD Performance Are Sometimes Inversely Correlated on Real-world Datasets. That paper shows that in misspecified settings, higher in-distribution accuracy can select less robust models. Our proxy keeps the cheapness of low-fidelity training but changes what is read out.

Research Program

The first deliverable is a ground-truth benchmark, because none exists for worst-group accuracy across architectures. We sample a few hundred cells from the NAS-Bench-201 space, introduced to the zero-cost literature by Zero-Cost Proxies for Lightweight NAS. We stratify by parameter count so that size does not explain everything. We train each cell from scratch to convergence on Waterbirds, CelebA (Blond/Gender), Colored MNIST and NICO at reduced resolution, with three seeds each. For every trained network we record average accuracy, worst-group accuracy under plain training, worst-group accuracy after a full last-layer refit, and worst-group accuracy under majority subsampling.

The benchmark answers a scientific question in its own right. The Effect of Model Size on Worst-Group Generalization finds that size helps pre-trained models but does little from scratch. Sagar et al. find that width hurts from scratch. The benchmark tests whether wiring explains worst-group accuracy beyond parameter count when trained from scratch. If it does not, architecture search for this problem is pointless. That would be a publishable negative result, and it stops the rest of the program.

The second deliverable is the proxy and its cost profile. For each candidate we compute $S(a,t)$ over a grid of training lengths. We measure how early the ranking stabilizes, reporting both FLOPs and wall-clock time. Zero-Cost Proxies for Lightweight NAS documents that a 64× FLOP reduction gave only a 4× real speedup, so FLOPs alone would overstate savings.

The label-free variant replaces true groups with inferred ones. Following the logic of Repeated Environment Inference for Invariant Learning, one fixed, intentionally biased model is trained once. Its errors on the training set define pseudo-minority groups. Both the balanced refit set and the worst-group readout are then built from these pseudo-groups. This model is shared across all candidates, so its cost is paid once.

The third deliverable is an actual search. Regularized evolution over the same space uses $S(a,t)$ as fitness. The top candidates are trained fully and compared at matched parameter budgets.

Baselines

The naive reference point is to train a hand-designed ResNet-18-scale network from scratch with ordinary training, or with majority subsampling, and do no search at all. Every searched network must beat this at equal or smaller parameter count. Sagar et al. report a from-scratch, overparameterized network with subsampling at 15.1% worst-group error on CelebA, using 3.4% of the data. On Waterbirds they report roughly 10–15%. We rerun this recipe at our resolution and training budget rather than copying numbers across setups.

The strongest existing ranking methods are the zero-cost proxies and their voting ensemble from Zero-Cost Proxies for Lightweight NAS. That ensemble reaches Spearman 0.82 against in-distribution accuracy on NAS-Bench-201. Lacuna has no reported result for any proxy's rank correlation with worst-group accuracy. We also run the adversarial proxy $R$ from Zero-cost Proxy for Adversarial Robustness Evaluation and the Fishr-at-initialization gradient-variance gap. We include parameter count and FLOPs because Vision Transformer Neural Architecture Search for Out-of-Distribution Generalization found them to be the strongest cheap predictors of shift robustness.

The most dangerous baseline is short-training in-distribution validation accuracy at exactly the same $t$. It costs the same as our proxy and is the default low-fidelity estimator.

The key ablation isolates the refit. At the same checkpoint we score candidates three ways: by in-distribution accuracy, by the trained head's own worst-group accuracy, and by the refit worst-group accuracy. If the second matches the third, the last-layer insight from Kirichenko et al. buys nothing at this stage of training.

All rankers see the same candidate pool, the same group-annotated validation split, and the same seeds. Each method's hyperparameters, such as minibatch size or refit regularization, receive the same small tuning budget on Colored MNIST before transfer to the other datasets. Beating the baselines means two things. First, a higher Kendall's τ with fully trained worst-group accuracy than both parameter count and short-training in-distribution accuracy, on at least three of four datasets, with seed-bootstrapped confidence intervals that exclude zero difference. Second, lower top-10 regret, defined as the gap between the best worst-group accuracy among the proxy's top ten and the true best, at no more than 10% of the cost of full training.

Why not just…?

Why not just take a large pre-trained ConvNeXt and refit its last layer? Kirichenko et al. report 97% worst-group accuracy on Waterbirds and 92% on CelebA this way, and we do not claim search competes with that when pre-training is allowed. This is a real threat. We answer it by scoping: our regime is small, from-scratch networks under a parameter budget, as in the embedded fingerprint setting of NAS-OoD and the low-power settings surveyed in A Survey of Methods for Low-Power Deep Learning and Computer Vision. In this regime, Neyshabur et al. find that size buys little and pre-trained backbones do not apply. We report the pre-trained number alongside ours so the reader sees the ceiling.

Why not just rank by parameter count? This is the baseline most likely to embarrass a new proxy, given the transformer-search findings. It is also ambiguous from scratch, since Sagar et al. show that more width can hurt worst-group accuracy. Our size-stratified sampling and partial correlations, controlling for parameters, settle whether the proxy carries information beyond size. If it does not, we report that architecture search adds nothing here.

Why not just subsample the majority group and use any architecture? Subsampling works but discards most of the data and needs group labels. More importantly, it is orthogonal to architecture choice. The benchmark records subsampled worst-group accuracy for every cell. This shows directly whether the architecture ranking is preserved under subsampling, in which case search and subsampling compose, or whether subsampling flattens architectural differences, in which case search is unnecessary once one subsamples.

Why not just use short-training validation accuracy, which costs the same? Teney et al. give a mechanism for its failure, but whether that failure occurs across architectures rather than across training runs is untested. The matched-cost comparison in our ablation is the direct test. If short-training accuracy ranks as well as our proxy, the refit is unnecessary and we will say so.

Decisive Checks

The program succeeds or fails on four checks. The first is whether fully trained worst-group accuracy varies across cells of equal size by more than seed noise. The second is whether $S(a,t)$ at about 5–10% of training beats both parameter count and matched-cost in-distribution accuracy in rank correlation. The third is whether the label-free variant retains most of that advantage. The fourth is whether evolution guided by the proxy finds networks that beat the subsampled ResNet-18 reference at fewer parameters on Waterbirds and CelebA.

We also inspect whether selected cells favour large receptive fields, as NAS-OoD's dilated-convolution finding predicts. This is a qualitative check that the proxy recovers a known shape-over-texture bias rather than an artifact like the skip-connection bias reported for the adversarial proxy. A negative outcome on the first check is itself informative. It would mean that from scratch and at small scale, worst-group robustness is set by data and training recipe, not wiring.