Cross-Episode Gradient Agreement: A Zero-Cost Architecture Score for Prototype-Based Few-Shot Learners

Few-shot learning asks a network to recognize new categories from one or a handful of labeled examples. The usual way to train for this is episodic meta-learning: the training data is cut into many small practice tasks ("episodes"), each with a few labeled examples and some held-out examples to classify, and the classes change from one episode to the next. The most widely used episodic learner, the prototypical network, labels a new image by finding the nearest class average ("prototype") in a learned embedding space. Its accuracy depends heavily on the shape of the embedding network, yet choosing that network by architecture search is expensive, because each candidate has to be meta-trained before it can be judged. Zero-cost proxies avoid this cost. They are scores computed on an untrained network in a single forward and backward pass. Every such proxy built for few-shot learning so far is derived from MAML, the method that adapts weights by gradient descent inside each episode. No proxy has been built for prototype-based learners.

We propose a score that asks the question episodic training itself asks: does a gradient step taken on one set of classes improve classification of a different, disjoint set of classes? At random initialization, we sample pairs of class-disjoint episodes, compute the prototypical loss on each, and measure how well their gradients agree. An architecture whose untrained gradients already point in shared directions across unrelated class sets should learn transferable metric features faster. We test whether this cross-episode gradient agreement ranks embedding architectures by their trained prototypical-network accuracy better than existing proxies, and better than counting FLOPs. We also test whether the ranking survives a shift to new image domains. To do this we build the ground-truth benchmark the field currently lacks: prototypical-network accuracies for about a thousand NAS-Bench-201 cell architectures.

Core Claim

Let $\theta$ be the randomly initialized weights of a candidate embedding network. Let $\mathcal{L}_e(\theta)$ be the prototypical-network loss on episode $e$: the cross-entropy of a softmax over negative squared Euclidean distances from query embeddings to support-set prototypes. Our score is

$$ \mathrm{CEGA}(\theta) = \mathbb{E}_{(e,e')}\left[\frac{\nabla \mathcal{L}_e(\theta)^\top \nabla \mathcal{L}_{e'}(\theta)}{\lVert\nabla \mathcal{L}_e(\theta)\rVert\,\lVert\nabla \mathcal{L}_{e'}(\theta)\rVert}\right], $$

where $e$ and $e'$ are episodes drawn with no classes in common, and the expectation is estimated over roughly 16 episode pairs.

The form follows from a first-order expansion. One gradient step of size $\eta$ on episode $e$ changes the loss on $e'$ by approximately $-\eta\,\nabla\mathcal{L}_e^\top\nabla\mathcal{L}_{e'}$. CEGA is therefore the initial rate at which learning one set of classes helps a different set, which is the property episodic training rewards. We use the cosine rather than the raw inner product on purpose. Gradient norms grow with parameter count, and the score should not inherit the "big model" bias that NAS-Bench-Suite-Zero found in many proxies.

The claim is falsifiable. CEGA must correlate with trained prototypical accuracy more strongly than FLOPs and than the best existing proxy. It must still correlate after FLOPs is partialled out. And its advantage must disappear when the episode structure is removed, which is the ablation that tests whether the advantage comes from the episodes.

Relation to Prior Work

Two papers motivate the gap and also supply the closest competitors. Global Convergence of MAML and Theory-Inspired NAS for Few-Shot Learning ranks untrained architectures using two quantities: the condition number of a meta neural tangent kernel, a kernel derived from MAML in the infinite-width limit under squared-error loss, and a count of linear regions. It cut search on miniImageNet from 168 to about 1.5 hours. Revisiting Neural Networks for Few-Shot Learning: A Zero-Cost NAS Perspective, which introduced IBFS, scores architectures by the entropy of the Jacobian's eigenvalues and justifies this through first-order MAML convergence. It reports a search time of 0.1 hours.

Both papers state that their results cover only MAML and that cross-domain behavior is untested. Our score needs no inner loop and no assumption of infinite width. It is computed through the actual prototypical cross-entropy, and it is evaluated against metric-based learners and under domain shift.

The relation to MetaNTK-NAS needs stating directly. Gradient inner products between episodes are entries of an empirical, finite-width tangent kernel. Our difference is to read off the cross-class-disjoint entries of the prototypical loss directly rather than the conditioning of the whole kernel. We will include MetaNTK-NAS as a baseline to show whether that difference matters.

The second group of papers constrains the design. NAS-Bench-Suite-Zero found three things across 28 search spaces and tasks: nwot (a score based on activation patterns at initialization) and FLOPs are the most robust single proxies; feeding several proxies into an XGBoost surrogate model raises Spearman correlation by up to 42%; and size bias is pervasive. IBFS, by contrast, claims nwot gives unstable rankings in few-shot settings. Our benchmark lets us settle this disagreement. We compute nwot on episodic batches and on ordinary batches and compare. On Random Weights and Unsupervised Feature Learning supplies the premise that much of an architecture's inductive bias is visible before training.

The method comes from Prototypical Networks. We use its learner: Euclidean prototypes and training with more classes per episode than are used at test time. We also use its miniImageNet protocol. The search space and its known pitfalls come from NAS-Bench-201, which shows that random search and regularized evolution are hard to beat.

We do not compete with H-Meta-NAS, which builds hardware-aware supernets for MAML, or with NFTS, which searches layer-wise fine-tuning policies for a fixed pretrained backbone using a meta-trained supernet. Both amortize an expensive supernet, while we target selection with no training at all. NFTS's cross-domain benchmarks do, however, provide our domain-shift test.

Research Program

The first deliverable is the ground-truth benchmark, which we call ProtoBench-201. We sample 1,000 NAS-Bench-201 cells, stratified by FLOPs so that size alone cannot explain the ranking. We stack each cell into a fixed-depth embedding network and train it as a 5-way 5-shot prototypical network on miniImageNet. Every architecture gets the same schedule and the same seeds, and we use 20-way training episodes following Snell et al. Images are downsampled to keep the cost near one GPU-hour per architecture, and three seeds are run for a 200-architecture subset to estimate noise. We check that the cheaper protocol preserves the ranking by retraining 50 architectures at full 84-pixel resolution and measuring rank correlation between the two settings.

Each architecture is then evaluated on held-out miniImageNet classes, and, without any further training, on episodes from Meta-Dataset and Meta-Album domains far from ImageNet. These include sketches, traffic signs, microscopy and remote sensing. This gives an in-domain ranking and several shifted rankings for the same architectures.

The second deliverable is the proxy study. We compute CEGA and the competing proxies on all 1,000 untrained networks and measure Spearman and Kendall rank correlation against trained accuracy, along with the partial correlation after controlling for FLOPs. We also compute CEGA using episodes drawn from the target domain's own few-shot data, which is labeled and available at test time. This tells us whether a score taken in seconds on target data recovers the ranking under shift.

The third deliverable embeds CEGA into regularized evolution as a cheap filter and measures the accuracy of the final architecture against search cost in GPU-hours.

Baselines

The naive reference points are a fixed hand-chosen architecture and random selection. The fixed architecture is the standard four-block convolutional embedding network that prototypical networks use. Random selection means picking one architecture uniformly from the 1,000. Its expected accuracy is the mean of ProtoBench-201, and its expected rank correlation is zero.

The strongest simple competitor is FLOPs. NAS-Bench-Suite-Zero found it among the two most robust single proxies, and size may dominate few-shot accuracy just as it often dominates supervised accuracy. FLOPs costs nothing to compute, so CEGA beats it only by showing higher rank correlation on the stratified sample and a partial correlation with accuracy that is clearly nonzero once FLOPs is controlled for.

The strongest existing zero-cost methods are nwot, IBFS and MetaNTK-NAS, along with the XGBoost ensemble of all thirteen NAS-Bench-Suite-Zero proxies. Each gets the same 16 episodes as CEGA, or the same images arranged as ordinary batches when that is how the proxy is defined, and each is computed on the same untrained networks. The ensemble is trained on the same number of labeled architectures we allow for any learned predictor. We will also report CEGA added as an extra ensemble feature.

For context on accuracy, Prototypical Networks report 68.20% for 5-way 5-shot on miniImageNet with the standard convolutional network. MetaNTK-NAS reports about 86.43% for 5-way 5-shot on tieredImageNet with a MAML learner in a different space. That second number is not directly comparable, but it marks what training-free search achieved for MAML. We found no reported result on Lacuna for any zero-cost proxy's rank correlation with trained prototypical-network accuracy, so we will establish these numbers ourselves.

The training-based competitor is budgeted performance estimation in the sense of Rethinking Performance Estimation in NAS, where each candidate gets a short episodic training run. It is matched to CEGA in wall-clock time and also given ten times that budget. Beating it at equal compute is the target. Matching it at one tenth of the compute is still a useful result.

Two ablations isolate the key ingredient. The first computes CEGA on ordinary fixed-label minibatches with a linear head, which removes the episode structure. The second computes CEGA with $e'$ drawn from the same classes as $e$, which removes the class-disjoint transfer the score is meant to measure. If either ablation scores as well as full CEGA, the episodic framing is not what drives the score.

Why not just…?

Why not just rank by FLOPs or parameter count? This is the most serious threat. If few-shot prototypical accuracy is mostly a function of capacity, a more elaborate proxy adds nothing. The FLOPs-stratified sampling and the partial-correlation analysis are designed to answer this. If CEGA's partial correlation with accuracy is near zero once FLOPs is controlled for, we will report that capacity is sufficient for this space and that the existing MAML-derived proxies may be measuring size as well.

Why not just use the existing NAS-Bench-201 supervised accuracy as the ranking? The lookup table already gives ImageNet-16-120 accuracy for every cell, and IBFS's argument that large-scale supervised design transfers poorly to few-shot learning was made for MAML, not prototypes. We will report the rank correlation between the table's accuracy and ProtoBench-201 accuracy. If it exceeds CEGA's in domain, the case for a dedicated proxy rests on the cross-domain results alone, and we will say so.

Why not just run regularized evolution with short episodic training? NAS-Bench-201 shows that simple evolutionary search is competitive, and a few hundred episodes of training may rank architectures well enough. The equal-compute comparison above settles this. The likely outcome is that short training wins at large budgets, and CEGA's value is as a pre-filter that cuts the number of candidates that need training.

Why not just use the NAS-Bench-Suite-Zero ensemble? Ensembles of proxies are strong, but the surrogate needs labeled architectures from the target task, and that labeling is the cost we are trying to remove. We report the ensemble both with and without CEGA as a feature. Whether CEGA adds information beyond the other proxies is the useful outcome in either case.

Proposed Experiments and Decisive Checks

The primary check is in domain. On ProtoBench-201 miniImageNet 5-way 5-shot, CEGA should exceed FLOPs, nwot, IBFS and MetaNTK-NAS in Spearman correlation by a margin larger than the spread across seeds, which we estimate from the three-seed subset. Top-10 regret is the accuracy gap between the best architecture among the proxy's top ten and the best architecture overall. It should also improve. Both ablations should lose most of the gain.

The second check is the stability question. We compute nwot with episodic batches and with ordinary batches on the same networks. If the episodic version shows the high variance IBFS describes and the ordinary version does not, that reconciles IBFS with NAS-Bench-Suite-Zero.

The third check is cross-domain. We correlate proxy scores with accuracy on each Meta-Dataset and Meta-Album domain. Source-episode CEGA should degrade more gracefully than the MAML-derived proxies, and target-episode CEGA should recover part of the lost correlation. If no proxy beats FLOPs under shift, that negative result answers the open question IBFS leaves about cross-domain behavior.

Finally, the search experiment reports the best architecture found by CEGA-filtered evolution within one GPU-hour of scoring plus the training of a handful of finalists. It is compared against random search and budgeted evolution at the same total cost, scored by accuracy on held-out miniImageNet classes and the mean accuracy across shifted domains.