When Simpler Predictors Win: A Look at Bilinear Interpretable NAS

Introduction

Neural Architecture Search has spent much of its history chasing accuracy through increasingly elaborate machinery. Early reinforcement learning and evolutionary methods consumed GPU-years to find competitive classification models. Differentiable approaches like DARTS brought the cost down to days, then hours. But the predictor at the heart of most modern constrained NAS pipelines has trended in the opposite direction: more complex, more hyperparameters, more opaque. The implicit assumption is that architecture quality is a fundamentally complicated function and that approximating it well requires a heavy model such as a multilayer perceptron or a Gaussian process with a tailored kernel.

The paper BINAS: Bilinear Interpretable Neural Architecture Search by Nayman, Aflalo, Noy, Jin, and Zelnik-Manor challenges that assumption. Its central claim is that a deliberately simple bilinear accuracy estimator can match the predictive performance of these heavier models, while turning the constrained search into a tractable optimization problem with theoretical guarantees and, importantly, readable structure. This is a useful case study in how the right inductive bias can buy you more than raw capacity.

The Bilinear Formulation and Why It Matters

The technical core of BINAS is a decision to model both the accuracy estimator and the expected resource cost as bilinear functions of the architecture encoding. To understand why this is more than a cosmetic choice, it helps to recall how the search space is structured.

BINAS builds on a one-shot supernetwork, the same family of pretrained super-networks used by OFA and HardCoRe-NAS. The architecture is described by discrete design choices: which operations to use, the depth of each stage, and the width or expansion ratios. Sub-networks are sampled from the supernetwork and evaluated, and the contribution of individual design choices is measured directly. Rather than feeding a one-hot or learned encoding of the full architecture into an MLP, BINAS expresses the predicted accuracy as a sum of:

• Linear terms, capturing the marginal contribution of each individual design choice.
• Bilinear interaction terms, capturing how pairs of choices combine.

This structure is what makes the method interpretable. In an MLP predictor, the influence of, say, adding a layer to the third stage is entangled across nonlinear activations and is effectively unrecoverable. In a bilinear model, that influence is an explicit coefficient. You can read it off the fitted parameters.

The second payoff is optimization. Because both the accuracy objective and the latency constraint are bilinear (hence quadratic) in the architecture variables, the constrained search becomes an Integer Quadratic Constrained Quadratic Programming (IQCQP) problem. This is a well-studied class of problems. BINAS solves it with off-the-shelf components in a few CPU minutes, followed by a short fine-tuning step. Compare this to HardCoRe-NAS, which backpropagates through a supernetwork under latency constraints for several GPU hours, or OFA, which runs evolutionary search over a complicated MLP predictor with many hyperparameters to tune.

The contrast in resource profile is worth emphasizing. A search that runs in CPU minutes rather than GPU hours is not just cheaper; it is scalable across many target devices and latency budgets. If you need an architecture optimized for a particular CPU at a particular latency, and then another for an MCU, and another for a TPU, the marginal cost of each additional search collapses. This addresses one of the genuine practical pain points in deployment-oriented NAS.

Interpretability as a First-Class Result

Most NAS papers treat interpretability, if at all, as an afterthought. BINAS makes it a deliverable. The reported finding is concrete: in the examined search space, adding depth and width is more effective at deeper stages of the network and at the beginning of each resolution stage.

This is the kind of statement that almost never emerges from a black-box predictor, and it is worth taking seriously as a design rule. The observation that capacity pays off most at the start of each resolution block aligns with an intuition about information flow in CNNs. When the spatial resolution drops, the network is committing to a more compressed representation, and the transition is where representational capacity is most stretched. Investing parameters at that boundary plausibly preserves information that would otherwise be lost. The finding that deeper stages benefit more is also consistent with the broader literature suggesting that later layers carry more task-specific, semantically rich features.

I would add a note of caution here that the paper itself is careful about. These rules are specific to the examined search space. Bilinear interpretability tells you about the structure of the predictor over a particular parameterization of architectures, not a universal law of CNN design. The interaction terms are pairwise, which means the model cannot capture genuinely higher-order interactions among three or more design choices. If such interactions are important in a given space, the bilinear fit will absorb them imperfectly into the lower-order terms, and the resulting interpretation could be misleading even where the predictive accuracy remains acceptable.

The Broader Lesson and Some Skepticism

The work connects to a recurring theme in the NAS literature: gradient information as a proxy for architecture quality is unreliable. The paper cites the known inconsistencies, particularly the pathologies that arise with skip connections in differentiable search spaces, where the search can collapse toward trivial solutions. BINAS sidesteps this by not relying on gradient signal through the architecture parameters as its quality estimator. Instead it measures contributions by sampling sub-networks, which is a more direct, if more sampling-intensive, signal.

This is the inductive bias argument I find most compelling. The community has largely assumed that a more expressive predictor is a better predictor. BINAS demonstrates a case where a restricted hypothesis class that exposes structure matches the expressive one on the metric that matters, while delivering optimizability and readability for free. The constraint is not a limitation here; it is what makes the downstream problem solvable in closed analytical form.

That said, I want to register honest reservations. First, the claim that the bilinear predictor "matches" complex predictors deserves scrutiny in terms of ranking correlation, not just final-model accuracy, since NAS ultimately cares about correctly ranking candidates. A predictor that is slightly worse on rank correlation but vastly easier to optimize can still win overall, but the two effects should be disentangled rather than conflated.

Second, the quality of the entire pipeline rests on the one-shot supernetwork being a faithful proxy for the accuracy ranking of extracted sub-networks. This is an inherited assumption shared with OFA, SPOS, and FairNAS, and it is known to be imperfect. The bilinear formulation does not fix supernetwork bias; it builds on top of it. Any systematic distortion in the supernetwork propagates into the fitted coefficients and therefore into both the search result and the interpretability claims.

Third, IQCQP is generally NP-hard. The paper reports fast solution times with off-the-shelf solvers, which suggests the particular instances are well-behaved, but the worst-case scaling to much larger search spaces is an open question.

Conclusion

BINAS makes a clean argument that is easy to state and harder to internalize: in constrained neural architecture search, a simpler predictor can be the better predictor. By modeling accuracy and latency as bilinear functions of the architecture, the work converts an opaque, expensive search into an IQCQP that solves in CPU minutes, strictly satisfies hard latency constraints, and yields architectures comparable to or better than the state of the art.

The interpretability is the part I expect to age well. Even if future search spaces require richer predictors, the discipline of preferring formulations that expose structure, rather than defaulting to ever-larger black boxes, is a healthy corrective. The open questions I would most like answered are how far the bilinear approximation can stretch before pairwise interactions are insufficient, and whether the readable design rules it produces generalize beyond the specific search space studied. If they do, NAS would gain something it has mostly lacked: transferable design intuition rather than one-off architectures.