Grid-Interpolated Gaussian Process Surrogates for Cheap-Signal Architecture Search

Neural architecture search tries to find a good network design without training every candidate. It gets cheaper only when it can lean on cheap signals: scores computed from an untrained network ("zero-cost proxies"), accuracies after a few epochs of training, and a handful of fully trained models. The natural tool for combining these signals is a Gaussian process (GP), a Bayesian regression model that returns calibrated uncertainty along with its predictions. Current GP surrogates for architecture search, however, are fit only to the few hundred expensive evaluations. The cheap signals are either thrown away or merged in by hand-tuned rules, and the reason is cost: an exact GP scales cubically in the number of observations. We propose to learn a coordinate system for architectures that is very low-dimensional, with two or three learned axes plus one axis for training budget. On that grid we run structured kernel interpolation, a technique that approximates the GP by interpolating onto a regular grid so that the linear algebra reduces to fast Fourier transforms. The GP can then condition on every cheap observation, including proxy scores for all 423,624 NAS-Bench-101 cells and thousands of short training runs, and draw joint posterior samples over the entire candidate pool in near-linear time.

The claim to test is simple. Architecture search should be charged for training compute, not for surrogate arithmetic. A surrogate that can afford to absorb far more cheap evidence, and can afford a very large grid of inducing points so that it does not blur sharp optima, should reach low regret with fewer simulated GPU-hours than surrogates that see only expensive evaluations. The main risk is equally simple and is the first thing we test: architecture quality may not be representable in three dimensions.

What is new relative to the closest work

Structured kernel interpolation (SKI) was introduced in Kernel Interpolation for Scalable Structured Gaussian Processes (KISS-GP). It writes the covariance as $\tilde K = W K_{GG} W^\top$, where $K_{GG}$ is the kernel on a regular grid of $M$ points and $W$ is a sparse local interpolation matrix. This makes each matrix-vector product cost $O(N + M\log M)$. Three papers supply the method we reuse. Deep Kernel Learning. showed that a neural network can compress inputs into a bottleneck of five or fewer dimensions, where SKI stays tractable, and can be trained end to end by marginal likelihood. Its networks and data were ordinary regression problems, never architecture graphs. Scalable Log Determinants for Gaussian Process Kernel Learning. supplies the stochastic Lanczos estimator that makes hyperparameter learning linear-time. Faster Kernel Interpolation for Gaussian Processes shows that once $W^\top W$ and $W^\top y$ are computed in one pass, each solver iteration costs $O(M\log M)$ regardless of $N$. That property matters here, because proxy scores for a fixed search space are static and can be precomputed once.

On the architecture side, three GP surrogates motivate the proposal and also bound it. GP-NAS uses a hand-built kernel over categorical block choices. NAS-BOWL uses a Weisfeiler-Lehman subtree kernel on high-dimensional motif counts. Transfer NAS with Meta-learned Bayesian Surrogates meta-learns a deep-kernel GP with a graph encoder. All three run exact GP inference on high-dimensional representations, so all three are limited to the expensive evaluations they collect. ProxyBO is the closest competitor. It combines zero-cost proxies with a GP surrogate, but it does so through rank-based fusion and a decaying temperature, not by conditioning one probabilistic model on the proxy data. BANANAS argued that GPs are a poor fit for architecture search on grounds of scaling and representation, and replaced them with MLP ensembles. Our proposal takes that criticism seriously. We keep the GP but move the representation problem into a learned encoder and the scaling problem into a grid.

Two further papers constrain the design. Approximation-Aware Bayesian Optimization shows that inducing-point surrogates with a small budget smooth over sharp optima and mislead the acquisition step. This is the main argument for SKI over sparse variational GPs: in three or four dimensions a grid can hold hundreds of thousands of inducing points at negligible cost. Kernel interpolation generalizes poorly and The Price of Linear Time: Error Analysis of Structured Kernel Interpolation warn that interpolation error on too coarse a grid can hurt generalization, so we treat grid resolution as a variable to measure.

Core Claim

A graph encoder $g_w$ maps each architecture $a$ to coordinates $z = g_w(a) \in [0,1]^d$ with $d \le 3$. The encoder is trained on cheap signals only: zero-cost proxy vectors for the whole pool and low-epoch accuracies. We append a fidelity coordinate $s$, the log of the number of training epochs, and place a product kernel on the grid:

$$k\big((z,s),(z',s')\big) = k_{\mathrm{arch}}(z,z')\,k_{\mathrm{fid}}(s,s').$$

Here $k_{\mathrm{arch}}$ is a stationary kernel over the learned coordinates and $k_{\mathrm{fid}}$ is a stationary kernel over training budget. On a Cartesian grid, $K_{GG}$ is a Kronecker product of Toeplitz matrices. The GP can therefore condition on every proxy-derived and low-fidelity observation. Joint posterior samples over the entire pool come from one grid sample followed by one sparse interpolation. The approach makes three testable predictions. First, an encoder with $d \le 3$ loses little top-tail ranking information relative to a high-dimensional exact-GP surrogate at the same data. Second, conditioning on the cheap data lowers regret per unit of simulated training compute. Third, at matched surrogate cost, a fine grid preserves top-$k$ ranking better than a sparse variational GP.

Research Program

We build the surrogate in three stages. In the first stage we pretrain the encoder. A small graph neural network over the cell DAG produces $d$ coordinates squashed into the unit cube. It is trained by maximizing the SKI marginal likelihood, computed with stochastic Lanczos, on proxy scores (snip, synflow, jacob_cov, following ProxyBO's set) and on whatever low-fidelity accuracies the search has bought so far. Because the encoder sees raw proxies as regression targets rather than as trusted rankings, it can learn to discount a proxy that is anti-correlated on a given space. ProxyBO documents exactly such a case: jacob_cov correlates negatively with accuracy on NAS-Bench-101.

In the second stage we freeze the encoder during search. The grid-structured GP then precomputes its summary statistics once and refits only kernel hyperparameters and the fidelity kernel as evaluations arrive. We re-fine-tune the encoder every fixed number of expensive evaluations.

In the third stage we choose actions. Acquisition is cost-aware Thompson sampling. We draw a joint posterior sample over all (architecture, fidelity) pairs in the pool and select the pair that maximizes the predicted gain at the top fidelity per unit of training cost. Training cost comes from the per-epoch times that NAS-Bench-101 tabulates.

Alongside search, we measure where the approximation breaks. We sweep $d$ from 1 to 4 and the points per axis $m$ from 16 to 128. For each setting we record the Kendall rank correlation within the true top 5%, the Kendall correlation over the full pool, and SKI interpolation error.

Baselines

The naive reference points are random search and regularized aging evolution (REA), both run with the same simulated compute accounting. NAS-Bench-201 shows these baselines often beat sophisticated methods. Beating them in regret per GPU-hour on every benchmark is the minimum requirement. For multi-fidelity cost, the matching reference is BOHB. NAS-Bench-101 reports that regularized evolution, BOHB and SMAC reached random search's final performance 5x faster. Because it already exploits low-epoch evaluations, BOHB is the fair test of whether our fidelity axis adds anything beyond successive halving.

The strongest existing method is ProxyBO, which reports a 70% reduction in test regret over the strongest baseline on NAS-Bench-201 CIFAR-100 and a 3.92× to 5.41× speedup over REA. We run it with its published proxy set, the same initial design, the same number of seeds, and the same compute accounting. Its original setting does not use low-fidelity training, so we also run a variant that is allowed to buy low-epoch evaluations, treating them as extra observations. This prevents our advantage from coming merely from access to a second fidelity. Beating ProxyBO means lower median regret at equal simulated GPU-hours on both NAS-Bench-201 CIFAR-100 and NAS-Bench-101, where ProxyBO has to cope with an anti-correlated proxy.

Among surrogate baselines we include BANANAS, a five-member MLP ensemble on path encodings, and NAS-BOWL, an exact GP with a Weisfeiler-Lehman kernel. Each gets the same evaluation budget, and each is also given the proxy scores as extra input features so that the comparison is about how cheap evidence is used, not whether it is used. For reference, BRP-NAS reports finding the top NAS-Bench-101 model after training 140 models.

Three ablations isolate the key ingredient. The first uses the same encoder and data with a sparse variational GP whose inducing count is set so that its per-step cost matches the SKI surrogate. This tests the representational-budget argument. The second uses the same encoder with an exact GP fit to a random subsample of the cheap data sized to match wall-clock time. This tests whether scale is needed at all. The third uses a 32-dimensional encoder with an exact GP trained on expensive data only, a TNAS-style surrogate without meta-training. This measures what the three-dimensional bottleneck costs.

Why not just…?

Why not just use an exact GP, since a few hundred evaluations cost milliseconds? For expensive evaluations alone, that is correct, and our proposal would be pointless. The argument only holds if the surrogate conditions on tens of thousands of cheap observations and samples jointly over hundreds of thousands of candidates, and those are the regimes where exact inference stops fitting in memory. The subsampled exact-GP ablation settles the question directly. If a wall-clock-matched subsample performs as well, conditioning on all the cheap data is unnecessary, and we will report that result.

Why not just use a sparse variational GP, which already scales linearly? It does scale, but its inducing budget is small. Approximation-Aware Bayesian Optimization shows that a small budget smooths away sharp optima, and top architectures sit in a sharp upper tail. In three or four dimensions SKI can afford a far larger budget at the same cost. The matched-cost ablation and the top-5% rank metric test this. This alternative is a real threat when $d$ is small and the objective surface is smooth, and we expect the gap to narrow there.

Why not just feed proxies into an MLP ensemble such as BANANAS? Ensembles scale well with SGD and accept graph encodings natively. What they do not provide is joint posterior samples across the pool or a principled model of how accuracy changes with training budget. The augmented BANANAS baseline receives the same proxy features and the same compute. If it matches our regret, the GP machinery adds no value on these benchmarks.

Why not just filter with zero-cost proxies? ProxyBO shows that proxy reliability flips sign between NAS-Bench-201 and NAS-Bench-101. Pure filtering on NAS-Bench-101 is therefore included as a baseline mainly to confirm this failure under our compute accounting.

Proposed Experiments

The testbeds are NAS-Bench-201 (15,625 architectures on CIFAR-10, CIFAR-100 and ImageNet-16-120, with best accuracies of 94.37%, 73.51% and 47.31% as reported by NAS-Bench-201) and NAS-Bench-101 (423,624 architectures with 4, 12, 36 and 108 epoch budgets and a best mean test accuracy of 94.32% per NAS-Bench-101). NAS-Bench-101 carries the main claim, because its pool size and multi-fidelity tables are where scale and cost accounting actually matter. NAS-Bench-301 is a stretch target, and we found no reported result on Lacuna for ProxyBO on NAS-Bench-301. Metrics are test regret against cumulative simulated training time, top-5% Kendall correlation, surrogate wall-clock per step, and calibration of predictive intervals. We run 30 seeds per method.

The first decisive check comes before any search. If the encoder with $d \le 3$ falls clearly below the 32-dimensional exact GP on top-5% rank correlation at equal data, the grid idea fails for architectures. We would then report that as the finding about how intrinsically dimensional architecture quality is.

The second check asks whether the full method beats ProxyBO and BOHB in regret per GPU-hour on NAS-Bench-101. The third asks whether the SKI surrogate beats the matched-cost sparse variational GP in the top tail, and whether that gap grows with $m$, as the smoothing argument predicts.

The fourth check covers robustness. We add a deliberately anti-correlated proxy and verify that the learned encoder discounts it, whereas rank fusion degrades.