Architecture Search Has a Training Problem

TL;DR for operators

Neural architecture search is not simply a process for selecting layers, connections, and activation functions. It is a process for comparing trained architecture–weight pairs.

That distinction matters because an architecture evaluated with poorly optimized weights may look worse than an inferior architecture whose weights happened to train faster. A search system can therefore become very efficient at ranking the wrong candidates.

The paper organizes NAS methods around two broad philosophies.¹

• Sampling-based methods generate candidate architectures, train or approximate them, and use the observed performance to decide what to try next.
• Bilevel theory-based methods explicitly model architecture selection as an outer optimization problem whose outcome depends on an inner weight-training problem.

The paper’s literature comparison suggests that differentiable and one-shot approaches have moved the field from searches measured in thousands of GPU-days toward searches measured in single-digit GPU-days—or less—while preserving competitive benchmark accuracy. Those figures should not be treated as a clean league table, because they come from different studies, hardware, search spaces, and training procedures.

The more controlled evidence concerns auxiliary-program NAS. Under similar CPU evaluation budgets, the reported LP-DARTS and SOCP-DARTS variants substantially outperform standard DARTS on CIFAR-10 and remain competitive when transferred to ImageNet. Their distinguishing idea is not merely “use second-order information.” It is to update the architecture while preserving, or subsequently restoring, the optimality of the model weights.

For businesses, the decision is therefore not “Should we automate architecture design?” It is:

How much approximation can we tolerate between the architecture we are evaluating and the model that architecture would become after proper training?

Cheap search is useful. Cheap search that systematically misranks candidates is merely an automated way to create technical debt.

Architecture quality does not exist independently of training

Suppose an engineering team is comparing two model architectures.

Architecture A reaches reasonable accuracy after five epochs. Architecture B trains slowly at first but eventually generalizes better. If the team evaluates both after five epochs, A wins. If both are trained properly, B wins.

Nothing mysterious happened. The evaluation protocol answered a different question:

• “Which architecture looks best under partial training?”
• rather than “Which architecture produces the best trained model?”

Neural architecture search industrializes this problem. Instead of comparing two candidates, it may compare thousands or millions. Every shortcut used to evaluate those candidates—early stopping, shared weights, surrogate scores, reduced datasets, zero-cost proxies—changes what the system is actually ranking.

The paper’s central correction is that NAS should be understood as a coupled optimization problem. Let $\alpha$ represent architecture parameters and $w$ represent model weights. A standard formulation is:

subject to

The outer problem selects the architecture using validation performance. The inner problem trains the weights associated with that architecture.

The notation $w^\ast(\alpha)$ carries most of the intellectual burden. It says that the weights used to judge an architecture are not arbitrary weights. They are the result of optimizing the training loss for that architecture.

Change $\alpha$, and the weight-training problem changes with it.

This is why architecture search cannot be reduced to ordinary parameter training. The architecture shapes the loss surface on which the weights are optimized. The resulting weights then determine the validation loss used to judge the architecture. The alleged “hyperparameter” is redesigning the problem that produces its own evaluation.

Convenient.

Sampling methods search candidates; bilevel methods search responses

The paper divides the NAS landscape into sampling-based and bilevel theory-based approaches. The distinction is more useful than a catalogue of algorithm names because it reveals where each method spends computation and where it accepts approximation.

Sampling methods treat architecture evaluation as an activity performed repeatedly. Bilevel methods treat the training response itself as mathematical structure that can be differentiated, constrained, approximated, or locally preserved.

That does not make sampling primitive. Random search remains a strong baseline because many large spaces have low effective dimensionality: only a subset of choices materially affects performance. Evolutionary methods remain attractive for irregular discrete spaces and competing objectives such as accuracy, latency, memory, and energy use.

The trade-off is evaluation cost. A sampler learns by observing candidate outcomes. If each outcome requires training a model, the search budget becomes a multiplication problem with an unpleasant number of zeros.

Approximate training reduces the zeros. It can also reduce the reliability of the ranking.

Black-box NAS pays repeatedly for incomplete answers

Early NAS systems demonstrated that automated search could discover competitive architectures. They also demonstrated that sufficient compute can make almost any research programme look elegant.

The paper’s literature table reports NASNet-A at 2,000 GPU-days and AmoebaNet-A at 3,150 GPU-days of search. Their reported CIFAR-10 accuracies were 97.35% and 96.66%, respectively. DARTS reported 97.24% with four GPU-days. PC-DARTS reported 97.43% with 0.1 GPU-days.

The striking result is not that one method wins by a few tenths of a percentage point. It is that continuous, differentiable search reduced the reported compute requirement by orders of magnitude while remaining in the same broad accuracy range.

These figures explain the field’s movement away from fully discrete black-box search. They do not prove that PC-DARTS is universally better than NASNet-A.

The rows come from separate studies. They involve different implementations, search spaces, hardware, training recipes, augmentation policies, and possibly different conventions for counting search cost. The table is best read as evidence of a historical change in the compute frontier, not as a procurement spreadsheet.

The direct business interpretation is narrower and more useful: repeatedly training independent candidates is unlikely to be an economical default when architecture choices can be relaxed, shared, or optimized more directly.

Differentiable NAS replaces enumeration with a trainable mixture

DARTS changes the architecture search problem by temporarily replacing a discrete choice with a continuous mixture.

Suppose an edge in a neural network could contain a convolution, pooling operation, skip connection, or no connection. A discrete search method selects one operation and evaluates the resulting network. DARTS assigns learnable weights to all candidate operations and represents the edge as their weighted combination:

The architecture parameters $\alpha$ now live in a continuous space. Gradient-based optimization becomes possible.

During search, DARTS alternates between two updates:

1. Update model weights using the training loss.
2. Update architecture parameters using the validation loss.

After optimization, the mixed edge is converted back into a discrete one, generally by selecting the operation with the largest architecture weight.

This relaxation is the source of the efficiency gain. The search no longer needs to instantiate and fully train every architecture separately.

It is also the source of new approximation problems.

The mixed network used during search is not identical to the final discrete network. The weights are not necessarily at their exact optimum each time the architecture changes. A one-step or truncated approximation may be used to estimate how the trained weights would respond. The architecture can therefore exploit weaknesses in the search procedure rather than identify a genuinely strong discrete design.

DARTS variants address these failures through progressive search spaces, partial channel connections, regularization, stochastic updates, operation-selection rules, dynamic sampling, and other repairs. The number of repairs is informative. Continuous relaxation solves the enumeration problem; it does not abolish the ranking problem.

Hypergradients account for how weights move when architecture changes

A naïve architecture update would differentiate validation loss directly with respect to $\alpha$ while treating $w$ as fixed. That captures the immediate effect of changing the architecture but ignores the fact that the weights would subsequently retrain.

Hypergradient methods attempt to include both effects:

The first term measures the direct effect of changing the architecture. The second measures the indirect effect transmitted through the optimal weights.

This is the mathematical version of a basic operational question:

If we change the system design, how will the trained system respond?

Hypergradients can be approximated through unrolled optimization, implicit differentiation, automatic differentiation, or finite differences. The more accurately the method models the inner training response, the more computation and memory it generally requires.

First-order approximations are cheaper. Second-order approximations contain more information about how architecture and weight optimization interact. Neither is magical. Both depend on local information, regularity assumptions, numerical stability, and the quality of the current inner solution.

The paper’s next contribution is to sharpen this issue. Rather than merely estimating a gradient that anticipates weight movement, auxiliary-program NAS explicitly searches for an architecture–weight update direction consistent with the lower-level optimality condition.

AP-NAS treats weight optimality as a constraint, not a suggestion

At a lower-level optimum, the gradient of the training loss with respect to the weights is zero:

If the architecture changes by a small amount $d_\alpha$, the weights must also change by $d_w$ to remain on the lower-level optimum manifold. Differentiating the condition gives the local relationship

Auxiliary-program NAS uses this relationship as a constraint while searching for a direction that decreases validation loss.

Conceptually, the update problem becomes:

subject to the linearized lower-level optimality condition and a bound on the update size.

With a Euclidean norm bound, the auxiliary problem can be expressed as a second-order cone program. Replacing that norm with a box constraint yields a linear program. The paper discusses these implementations as SOCP-DARTS and LP-DARTS.

The difference from an ordinary hypergradient update is subtle but important.

A hypergradient method computes an architecture direction informed by the anticipated weight response. Once the architecture is updated, however, the current weights may no longer be optimal for the modified architecture.

AP-NAS computes architecture and weight directions together so that the update locally preserves the inner optimality condition. Because the calculation is approximate, the method can then retrain the weights from a warm start to restore that condition more accurately.

In other words, it does not pretend that architecture can move while training politely remains solved.

Second-order information is useful until it meets model scale

The auxiliary constraint contains Hessian information. For realistic neural networks, constructing and storing a full Hessian is generally impractical.

The paper describes several compromises:

• L-BFGS approximations that use a limited history of parameter and gradient updates;
• rank-one approximations constructed from successive optimization steps;
• reduced Hessians computed for only a subset of model parameters;
• deterministic parameter selection using gradient norm per parameter;
• random subset selection to broaden coverage across iterations.

LP-DARTS selects influential parameter tensors using a normalized gradient-magnitude criterion. SOCP-DARTS samples from a constrained candidate set, reducing systematic preference for only the tensors with the largest current gradients.

These are not incidental implementation details. They determine which part of the weight response the auxiliary programme is capable of preserving.

The full theoretical condition concerns all model parameters. The practical algorithm observes a compressed approximation. AP-NAS is therefore more disciplined than simply ignoring the lower-level response, but it is not an exact solution to large-scale neural training.

The useful business reading is not “second-order optimization has solved NAS.” It is:

Curvature information can improve architecture updates, provided the organization can construct an approximation whose cost and bias are acceptable for the model scale.

That is a less marketable sentence. It is also the one that can survive contact with an infrastructure budget.

The constrained evaluation supports AP-NAS, not universal dominance

The paper’s most relevant AP-NAS evidence is the time-constrained comparison on CIFAR-10, followed by transfer evaluation on ImageNet.

DARTS, LP-DARTS, and SOCP-DARTS were searched and selected for approximately the same duration. The experiments were performed on CPUs. The table also includes P-DARTS, PC-DARTS, and two STO-DARTS variants, although their architectures were taken from their original publications rather than rediscovered under precisely the same search process.

That distinction matters when interpreting the table.

LP-DARTS exceeds standard DARTS by 9.99 percentage points on CIFAR-10 while using roughly the same reported evaluation time and fewer parameters. SOCP-DARTS exceeds it by 7.99 points and records the strongest ImageNet top-1 result among the three directly searched DARTS variants.

The purpose of this table is main comparative evidence under a bounded compute setting. It supports the claim that auxiliary-program updates can improve standard DARTS when search resources are constrained.

It does not establish that LP-DARTS or SOCP-DARTS dominates every modern NAS method. Nor does it isolate precisely which component creates the gain: lower-level feasibility, curvature information, parameter subset selection, step-size choice, or interactions among them.

The comparison with architectures imported from other publications is useful context, but it is not a fully controlled head-to-head experiment. Those architectures benefited from their original tuning processes and computational environments.

The sensible conclusion is competitive performance under constraints, not coronation.

The paper’s evidence serves four different purposes

Several results in the paper can look equally authoritative because they all arrive in tables. They are not answering the same question.

The hyperlocal-search results are particularly easy to overread. The paper reports that applying local joint refinement after grid, random, TPE, or quasi-Monte Carlo search consistently improves CIFAR-10 test accuracy in the shown settings. It also discusses prior GPT-2 Small experiments in which hyperlocal search reduces test perplexity increasingly as overfitting becomes more severe.

These findings extend the mechanism from architecture parameters to regularization and fine-tuning hyperparameters. They are evidence that the auxiliary-program idea is broader than NAS. They are not a second independent demonstration that AP-NAS wins architecture-search benchmarks.

An exploratory extension can be valuable without being promoted to a second thesis. Research papers occasionally survive this restraint.

Choose the search method by the approximation you can defend

The paper’s taxonomy becomes operational when translated into four questions.

Is the search space differentiable or meaningfully relaxable?

If architecture choices can be represented by continuous mixtures without destroying the relevant deployment constraints, hypergradient-based NAS becomes attractive.

If the search space contains hard compiler choices, branching structures, quantization modes, device-specific kernels, or other irregular discrete decisions, evolutionary, reinforcement-learning, or Bayesian strategies may remain more appropriate.

A continuous relaxation is useful only when performance in the relaxed search system correlates with performance after discretization.

Can candidate evaluations share training?

One-shot and supernet methods reduce cost by training a larger network whose subnetworks inherit weights. This can make evaluation dramatically cheaper.

The risk is ranking inconsistency: inherited weights may favor subnetworks that cooperate well inside the supernet rather than subnetworks that perform best when trained independently.

For early screening, that may be acceptable. For an expensive production commitment, the finalists should be retrained independently.

How costly is a wrong ranking?

When the selected model will be deployed across millions of devices, used as a long-lived platform component, or retrained repeatedly, additional search rigor may pay for itself.

When the model is temporary, the dataset is drifting rapidly, or the deployment volume is small, a sophisticated architecture search may cost more than the architecture is worth.

NAS should be evaluated against credible alternatives: a known architecture, scaling-law-informed design, pruning, distillation, quantization, adapter tuning, or simply better data.

Can the team validate the inner optimization assumption?

Bilevel formulations assume that each architecture is associated with an adequately optimized lower-level model. Real training pipelines stop early, encounter stochasticity, and land in different local solutions.

The paper notes that multiple weight configurations may achieve the same training loss. Standard NAS practice generally treats the resulting reaction as effectively unique or adopts an optimistic interpretation: among equally optimal weight solutions, the one favorable to validation performance is selected.

Operationally, this means random seed, optimizer configuration, and training schedule are not harmless details. They influence which lower-level response is observed.

A production NAS pipeline should therefore test whether architecture rankings remain stable across retraining runs. Otherwise, it may be optimizing the seed-selection policy with architecture-themed decoration.

The ROI is fewer misleading experiments, not merely fewer experiments

The most obvious economic argument for differentiable NAS is lower compute. That is incomplete.

The more important value is reducing the number of candidate evaluations that provide misleading information.

Consider four costs:

Search compute is the easiest item to measure. Selection error may be more expensive.

A weak architecture can often be detected. A misranked architecture is harder: it arrives with benchmark results, an experiment log, and the institutional confidence generated by automation. The system did not merely make a mistake. It produced paperwork.

For teams building reusable model families, on-device systems, or repeated task-specific deployments, the paper suggests three practical layers:

1. Use cheap sampling, weight sharing, or proxies to narrow the space.
2. Apply bilevel or hypergradient refinement where the architecture is differentiable.
3. Independently retrain and evaluate a small finalist set under the actual deployment recipe.

AP-NAS fits most naturally in the second layer. It is a local refinement framework, not an argument for searching the entire universe with a Hessian.

The paper is a framework and synthesis, not a universal benchmark

Three boundaries should shape any implementation decision.

First, much of the broad accuracy-and-cost evidence is compiled from prior studies. The results support a field-level transition toward differentiable, hardware-aware, and one-shot methods, but they do not provide a standardized experimental comparison.

Second, the controlled AP-NAS evidence is bounded. It uses CIFAR-10 search, ImageNet transfer, DARTS-derived spaces, limited compute, and CPU-based evaluation. These conditions are useful precisely because they test constrained search. They are not representative of every industrial architecture problem.

Third, AP-NAS depends on local approximations to second-order structure. Reduced Hessians, L-BFGS estimates, selected parameter tensors, and warm-start retraining make the method tractable. They also create approximation error. Scaling the idea to very large models will require structured curvature representations and careful decisions about which parameters deserve second-order treatment.

The paper itself points toward block-diagonal or staircase Hessian approximations, hybridization with other differentiable NAS methods, broader search spaces, and foundation-model applications.

Those are research directions, not completed deliverables.

Stop asking which architecture is best

The wrong question is:

Which architecture has the highest score?

The better question is:

Under what training response, search approximation, compute budget, and deployment constraint was that architecture judged?

Sampling-based NAS made automated architecture design possible. Differentiable and one-shot methods made it far cheaper. Bilevel optimization explains why the remaining difficulty is not merely navigating a large search space. It is preserving the relationship between a design and the trained model that gives the design meaning.

Auxiliary-program NAS pushes that logic further. Architecture updates should not be evaluated while the model weights are quietly becoming obsolete. The search direction should account for how the lower-level optimum moves—and, where possible, remain consistent with it.

For operators, the paper does not prescribe one universal NAS algorithm. It provides a better decision boundary.

Use black-box sampling when the space is irregular and evaluations are affordable. Use weight sharing when rapid filtering matters more than perfect ranking. Use differentiable search when the architecture can be relaxed credibly. Use auxiliary-program refinement when lower-level consistency is important enough to justify curvature approximations.

And always retrain the winner.

An architecture is not a model. It is a proposal for what a model might become after training. Neural architecture search is useful only when it remembers the second half of that sentence.

Cognaptus: Automate the Present, Incubate the Future.