Competitive Titration Scoring for Training-Free Architecture Search

Architecture search tries to pick the best building block for each slot of a neural network: a 3x3 convolution, a skip connection, pooling, and so on. Its cost comes from having to judge candidates. The cheapest judges are "zero-cost proxies," scores computed on an untrained network in one forward and backward pass. The best of these, Zero-Cost-PT, scores an operation by deleting it from a network that mixes all candidates and measuring how much the proxy drops. It searches NAS-Bench-201 in 0.05 GPU-days, but its authors concede that it is noisy and has no account of why it works (Zero-Cost Operation Scoring in Differentiable Architecture Search). Molecular biologists faced a similar measurement problem: deciding which of two proteins really owns a DNA binding site when every single readout is noisy. Their answer was not to knock a protein out and look once. They titrate. They add rising amounts of an unlabeled competitor against a labeled one, read the whole displacement curve, and express the result as a relative affinity, which cancels much of the noise the two measurements share. Competitive EMSA, a gel assay that shows which protein ends up bound to a DNA fragment, was used this way to show that the repressor XTR1 displaces the activator XYR1 from one 15-base motif (A novel transcriptional repressor specifically regulates xylanase gene 1 in Trichoderma reesei).

We propose to score candidate operations the same way. On each edge of the search cell, two operations at a time share the edge in proportions that sweep from 0 to 1, and we fit the training-free proxy along that sweep. The result is a matrix of pairwise "affinities" per edge. We expect this to rank operations more reliably than single knockouts at the same compute. The pairwise structure also yields a free reliability check: if the affinities are not transitive (A beats B, B beats C, C beats A), the proxy cannot be trusted on that edge. A small training budget can then go only to those edges, which turns the biological idea into a direct reduction in search cost.

Core Claim

The claim is narrow and testable. At matched numbers of forward and backward passes, pairwise titration curves give operation rankings with higher rank correlation to ground-truth accuracy, and lower variance across random initializations, than knockout scoring in the full mixture. Intransitivity in the pairwise affinities predicts which edges the proxy gets wrong.

The mechanism has two parts. First, a difference between two scores taken on the same initialized network cancels shared noise, as relative affinity does in a competition assay. Second, a fitted curve averages over many points instead of relying on one finite difference.

A further prediction comes from work on synthetic promoters. Sharon et al. found that putting more binding sites on a promoter makes proteins block one another and raises expression noise (Probing the effect of promoters on noise in gene expression using thousands of designed sequences). The analogue here is that proxy scores taken in a full mixture of five to eight operations should be noisier than scores taken in two-operation mixtures. We treat this as a hypothesis to measure, not as an assumption.

Formally, take an edge with incumbent operation $a$ and challenger $b$. We set the edge output to $(1-\lambda)\,a(x) + \lambda\, b(x)$ with $\lambda \in [0,1]$ and record the proxy $S_{ab}(\lambda)$ at $K$ values of $\lambda$, holding everything else in the network fixed. The affinity of $b$ over $a$ is the slope of a low-order polynomial fit,

$$A_{ab} = \frac{d\hat S_{ab}}{d\lambda}\Big|_{\lambda\in[0,1]} ,$$

averaged over the interval. Here $\hat S_{ab}$ is the fitted curve. Knockout scoring corresponds to one finite difference against the "zeroize" operation, so it is a special case of this measurement with $K=2$ and a fixed challenger.

Research Program

The biology serves as a lens on measurement design. It does not supply a simulation, which also answers the concern that molecular models are too costly to run inside search. Three roles are worth separating. Xu et al.'s competitive EMSA and Gao et al.'s occupancy readout, in which promoter occupancy by FOXP3 falls from 63.5% to 13.9% when Gal-1 masks its DNA-binding domain (Nuclear galectin-1-FOXP3 interaction dampens the tumor-suppressive properties of FOXP3 in breast cancer), supply the method: fractional occupancy read as a graded curve. Sharon et al. motivate the prediction about the number of competitors. Hufton et al.'s finding that steady states are robust while switching rates control dynamics (A stochastic and dynamical view of pluripotency in mouse embryonic stem cells) constrains the design. It suggests we should not expect titration to change which operation wins on clear-cut edges, only how reliably the winner is identified on contested ones.

The work has four parts.

  1. Scorer. We will build the scorer on top of existing proxies, including Zero-Cost-PT's and those that EZNAS evolves (EZNAS: Evolving Zero-Cost Proxies For Neural Architecture Scoring). Titration is therefore a wrapper that any proxy can sit inside.
  2. Affinity matrix and architecture selection. For each edge we compute the full pairwise matrix. We rank operations by a Bradley–Terry fit, a standard model that turns pairwise win margins into a single strength score per item. We measure intransitivity as the residual of that fit.
  3. Budget allocation. Edges whose intransitivity exceeds a threshold receive a short training-based estimate. Following budgeted performance estimation (Rethinking Performance Estimation in Neural Architecture Search), this means a few epochs of training on only those edges. All other edges are decided training-free.
  4. Analysis of where the gain comes from. We will decompose any gain into variance reduction, measured as seed-to-seed rank stability, and bias change, measured as systematic preference for skip connections. Skip-connection bias is the known failure mode of gradient-based search (Fair DARTS; DARTS-).

Baselines

Random architecture. The naive reference is a randomly drawn architecture from NAS-Bench-201, scored by table lookup. Below it on the ladder is "do nothing", since the gap between random and the benchmark optimum sets the scale of every improvement. The NAS-Bench-201 optimum is 94.37% / 73.51% / 47.31% test accuracy on CIFAR-10, CIFAR-100 and ImageNet-16-120 (NAS-Bench-201).

Zero-Cost-PT. The direct competitor is Zero-Cost-PT (Zero-Cost Operation Scoring in Differentiable Architecture Search). It is the strongest training-free operation scorer in the file and the method titration generalizes. We will run it with its own proxy and supernet. The key fairness rule is that its total pass count is raised to equal ours, by averaging knockouts over extra initializations and minibatches. The file reports a 0.05 GPU-day search cost for it on NAS-Bench-201 but no per-dataset accuracy or Kendall tau. For those figures, no reported result was found on Lacuna, so we will reproduce them ourselves.

GAEA. The strongest accuracy baseline is GAEA (Geometry-Aware Gradient Algorithms for Neural Architecture Search). It runs exponentiated-gradient updates on the simplex of operation weights and reports 94.10% on CIFAR-10 and 73.43% on CIFAR-100 on NAS-Bench-201. It requires training a supernet, so the comparison is on accuracy per GPU-hour, not raw accuracy.

What counts as beating them. We beat Zero-Cost-PT if we get higher Kendall tau and higher final accuracy at equal passes. We beat GAEA if we come within its accuracy (≥94.10% / ≥73.43%) at a fraction of its search cost.

Ablations. Two ablations isolate the key ingredients. Titration with $K=2$ tests whether the curve matters or the pairing alone does. Titration whose only challenger is "zeroize" tests whether pairwise competition matters, since this is knockout scoring done with a dose sweep.

Why not just…?

Why not just average Zero-Cost-PT over more seeds with the same compute? This is the most serious threat. If our gain is only variance reduction, compute-matched averaging may recover it. The matched-pass baseline above is designed to settle exactly this question. Titration should win only if the paired difference cancels noise that independent repeats do not. If it does not win, we will report titration as no better than repetition.

Why not just fix collapse with Fair DARTS, DARTS-, or GAEA? These methods solve a different problem: bias inside a trained supernet. Fair DARTS uses independent sigmoids, DARTS- adds a decaying auxiliary skip path, and GAEA uses mirror descent on the simplex. They report strong numbers, for example 97.46% on CIFAR-10 for Fair DARTS and 97.41% for DARTS-. All of them pay for supernet training. Our question is how much of that accuracy survives without training. We compare on accuracy versus GPU-hours, not on accuracy alone.

Why not just train each candidate for a few epochs? Budgeted estimation (Rethinking Performance Estimation in Neural Architecture Search) is a real alternative and is already part of our pipeline for flagged edges. The test is whether intransitivity-targeted training beats spending the same budget uniformly across all edges.

Why not just cap the number of skip connections? A cap removes one known bias but does nothing for noise among the parameterized operations. The skip-bias analysis will show whether titration's gain is concentrated on skip-versus-convolution pairs. If it is, a cap would be a sufficient and simpler fix, and we will say so.

Proposed Experiments

Benchmarks and metrics. The main testbed is NAS-Bench-201 on all three datasets, because table lookup over its 15,625 architectures gives exact ground truth. We derive per-edge operation importance from the table and correlate it, using Kendall tau, with each scorer's rankings. We report seed-to-seed rank variance, final test accuracy of the selected architecture, and wall-clock cost. NAS-Bench-1Shot1 (NAS-Bench-1Shot1) tests whether the results hold in a second search space. A CIFAR-10 search in the DARTS space, followed by retraining, tests transfer outside tabular benchmarks, compared against GAEA's reported 2.50% error.

Decisive checks. Four results decide the outcome.

  1. Titration versus matched knockout. Titration must beat compute-matched Zero-Cost-PT on Kendall tau across at least two proxies and three datasets. If it does not, the core claim fails.
  2. Intransitivity as an error signal. Edges flagged as intransitive must have measurably higher scoring error than unflagged ones. If they do not, the budget-allocation component has no basis.
  3. Number of competitors. Proxy variance should rise with the number of operations mixed on an edge, as the promoter-noise result predicts. A flat relationship would remove the biological motivation but would not by itself invalidate the method.
  4. Hybrid cost and accuracy. The hybrid pipeline should reach GAEA-level accuracy on NAS-Bench-201 at under a tenth of GAEA's search cost.