Automated architecture search over expressive spaces is slow because nearly every candidate must be trained before anyone knows whether it is good. einspace defines such a space. It describes networks with a probabilistic context-free grammar, meaning a set of weighted rewrite rules that build a network out of branching, aggregation, routing and computation operations. Searching it found an architecture that beat ResNet18 by 5.76% on a language task, yet the evolutionary search still trains each mutated child network. Zero-cost proxies are scores computed from a single minibatch at initialization, and they are the standard way to skip training. They were built and tested only on small fixed-cell spaces, and Zero-Cost Proxies for Lightweight NAS already reports that some of them break down when networks do not share a common topology. That is exactly the situation in a grammar space.
Machine translation faced a similar problem two decades ago and found a good answer. Decoders that strictly required phrases to match parse-tree constituents threw away good translations, because parsers make mistakes and languages differ in structure. The fix was to turn syntax into a weighted feature in a log-linear score that strong lexical evidence could outvote (Marton; Cherry). We propose the same move for architecture search. A cheap but noisy zero-cost proxy plays the role of the lexical score. The grammar contributes a soft structural score: the probability of a candidate's derivation under rule probabilities re-estimated from the networks that have trained well so far. The two scores are combined with weights fitted to the few candidates actually trained, and the combined score decides which children of an evolutionary search get trained. No candidate is ever rejected outright.
Core Claim
In grammar-defined architecture spaces, a few-parameter log-linear ranker can cut the number of full trainings needed to match full-training regularized evolution in einspace. The ranker combines three ingredients: zero-cost proxies, a separately weighted size feature, and the log-probability of the derivation under an adaptively re-estimated grammar. We claim specifically that this soft combination beats two alternatives: proxy-only screening, and hard proxy-threshold pruning in the style of the zero-cost move proposals of Abdelfattah et al.. We expect the advantage to be largest early in search, when few labels exist.
The novelty is not "grammars for NAS", which einspace and Evolutionary Architecture Search through Grammar-Based Sequence Alignment already do. Both of those use the grammar only as a hard validity filter, with fixed rule probabilities or fixed edit costs. Nor is the novelty "proxies for NAS", since proxies have never been tested on grammar-generated networks. What is new is using grammar statistics as a learned, outvotable feature for deciding which candidates to train.
One possible version of this idea is wrong, and we avoid it. Making grammar validity itself soft would mean letting search produce programs with mismatched tensor shapes, which simply do not run. In our design, the grammar's hard type rules stay hard. Only the preference among valid derivations becomes soft. This is the faithful analogue of MT, where the soft constraint was always about preferring constituents, not about permitting ill-formed output.
Research Program
Measuring proxies on grammar-generated networks. The first step measures how the proxies behave on networks they were never designed for. We sample several hundred architectures per task from einspace, using both the base grammar and mutations of the ResNet18 and ViT seeds that einspace's RE(Mix) uses. We train each sampled network with the einspace protocol. We then compute the proxy suite of NAS-Bench-Suite-Zero on the same networks. This suite includes synflow, snip, grasp, fisher, grad_norm, jacob_cov and nwot, along with flops and parameter count. The output is a public table of trained einspace architectures together with Spearman and Kendall correlations per task. This directly tests Gap 3, the prediction that proxies degrade on heterogeneous topologies. The table is useful even if the method fails.
The ranker. For a candidate architecture $a$ with grammar derivation $d(a)$, we score
$$s(a) = \sum_k \lambda_k \, z_k(a) + \mu \log P_\theta(d(a)) + \nu \log n(a),$$
where the terms are defined as follows. The $z_k$ are rank-normalized zero-cost proxy values. $n(a)$ is the parameter count, given its own weight $\nu$ so that the proxies' known bias toward large models is modeled explicitly rather than corrected by a post-hoc penalty. $P_\theta$ is the grammar with rule probabilities $\theta$.
We re-estimate $\theta$ each generation from rule counts in the derivations of the top-performing trained architectures. These counts are weighted by validation rank and smoothed toward einspace's original probabilities. This is the grammar-side counterpart of the latent rule distributions of Huang et al.. It is also closely related to PARSEC's learned distribution over choices (Casale et al.), extended from fixed cell edges to grammar productions.
The weights $(\lambda, \mu, \nu)$ are fitted by pairwise logistic ranking loss on all trained candidates. This mirrors how MT systems tuned feature weights on development data. It also targets the weight-sensitivity problem the soft-constraint literature flags, because a handful of weights can be fitted from tens of labels.
Using the ranker during search. In each generation, regularized evolution proposes $N$ valid children. Of these, $m \ll N$ are trained. They are drawn by sampling without replacement from a softmax over $s(a)/T$, where $T$ is a temperature, rather than by taking the top-$m$. This keeps every child's chance of being trained above zero, which is what "soft" means operationally here.
Baselines
The naive reference point is einspace's own regularized evolution, RE(Mix), which trains every child under the same total GPU-hour budget. It tells us what screening costs or saves. The file's reported figure for the strongest version of this baseline is einspace's architecture outperforming ResNet18 by 5.76% on the Unseen NAS language task. For NinaPro, einspace reports a new best result over expert architectures, but no reported numeric value was found on Lacuna. We therefore rerun einspace on every task and compare against our own reproduced numbers. A tuned ResNet18 seed and a Wide ResNet are included as fixed-architecture references, following NAS-Bench-360's finding that a tuned Wide ResNet often beats NAS methods.
The strongest existing screening method is a surrogate predictor trained on the same labels and inputs used in NAS-Bench-Suite-Zero. That paper reports that surrogate models with zero-cost proxy features gain up to 42% in Spearman correlation. Concretely, this baseline is gradient-boosted trees on all proxy values plus generic graph features (depth, width, operation counts, flops, parameter count). It sees the same trained candidates at every generation and receives the same hyperparameter-tuning budget as our ranker, with tuning by cross-validation on the trained set.
The second existing method is hard screening: train only children whose proxy vote exceeds a percentile threshold. This follows the zero-cost moves of Abdelfattah et al., whose best proxy vote reached Spearman 0.82 on NAS-Bench-201.
Ablations isolate the key ingredient. We remove the grammar term ($\mu = 0$). We replace $P_\theta$ with the fixed einspace probabilities, which isolates adaptation. We replace sampling with top-$m$ selection, which isolates softness. We also add the grammar log-probability as a feature to the boosted-tree surrogate.
Beating a baseline means reaching RE(Mix)'s final accuracy with at least 2× fewer full trainings on a majority of tasks, counting proxy and wall-clock overhead. The comparison against the surrogate and the hard filter is final test accuracy at matched budget, with confidence intervals over five seeds.
Why not just…?
Why not just feed proxies into a boosted-tree surrogate, as NAS-Bench-Suite-Zero does? This is the real threat. If the surrogate given grammar log-probability as a feature matches our ranker, then our contribution reduces to "grammar statistics are a useful feature." That would still be worth knowing, but it is smaller than our claim. Our bet is that with 20–100 labels, a five-parameter ranker generalizes better than trees fitted over dozens of features. The learning-curve experiment below settles this by plotting ranking quality against the number of labels for both models.
Why not just prune children whose proxy score is low? The MT experience in Cherry shows that hard filters on noisy structural signals systematically discard good non-standard outputs. Proxies are a noisy signal, and NAS-Bench-360 reports they are especially unreliable outside vision. We measure this directly: what fraction of each run's eventual top-10 architectures a hard threshold would have rejected at birth.
Why not just sample from the re-estimated grammar and drop proxies entirely? That is a distribution-learning search in the spirit of PARSEC. It is cheap and needs no initialization-time scoring. The $\lambda = 0$ ablation is exactly this method. If it wins, proxies add nothing in grammar spaces, and we would report that as the finding.
Why not just train each candidate for fewer epochs? Reduced training is the obvious alternative to proxies. Abdelfattah et al. found that a reduced-training proxy, EcoNAS, reached only 0.61 Spearman at far higher cost than proxy voting. We still include a one-epoch reduced-training ranker as a feature-free comparison on our trained-architecture table.
Proposed Experiments
The main benchmarks are the Unseen NAS tasks used by both grammar-based papers: AddNIST, MultNIST, CIFARTile, Gutenberg, Language, Isabella, GeoClassing and Chesseract. We add NinaPro, ECG and Darcy Flow from NAS-Bench-360 to probe the cross-domain failure of proxies. NAS-Bench-201 serves as a sanity check where ground truth is free. There the grammar is degenerate, so we expect the grammar term to contribute little and our ranker to roughly match the reported 0.82 proxy vote.
The decisive checks are three. First, the proxy correlation table on einspace: if proxies are near zero on most tasks, screening cannot help, and the paper becomes a negative result about proxies in open-ended spaces. Second, ranking quality on held-out trained architectures as a function of label count, for our ranker, the surrogate, and the ablations. The grammar term must add measurably over size plus proxies, or the soft-syntax framing is not supported. Third, end-to-end search on matched GPU-hours, reporting final test accuracy, number of full trainings needed to reach RE(Mix) accuracy, and measured wall-clock rather than FLOPs, because of the GPU gap that Abdelfattah et al. document. A secondary analysis compares how often top architectures under hard versus soft screening fall outside the high-probability region of the original grammar. This tests whether soft scoring preserves unusual winners the way it preserved non-constituent phrases in translation.
References
- einspace: Searching for Neural Architectures from Fundamental Operations
- Zero-Cost Proxies for Lightweight NAS
- Soft Syntactic Constraints for Hierarchical Phrased-Based Translation
- Cohesive Phrase-Based Decoding for Statistical Machine Translation
- Evolutionary Architecture Search Through Grammar-based Sequence Alignment
- NAS-Bench-Suite-Zero: Accelerating Research on Zero Cost Proxies
- Soft Syntactic Constraints for Hierarchical Phrase-Based Translation Using Latent Syntactic Distributions
- Probabilistic Neural Architecture Search
- NAS-Bench-360: Benchmarking Diverse Tasks for Neural Architecture Search
- A Comparison of Syntactically Motivated Word Alignment Spaces