Most gradient-based architecture search fixes the order in which a network's pieces run and learns only what sits on each connection. When every node in the search graph is an interchangeable placeholder, that is a harmless convention: any wiring can be relabeled to fit the fixed order. Many real design questions are different. The candidate blocks already have identities, such as a convolution, an attention layer, a pooling step, or a squeeze-excitation gate, and the open question is which block should run before which, and which earlier outputs each block should read. That is an ordering problem over labeled items. It is structurally the same problem causal discovery solves when it learns an ordering of named variables. This note proposes importing the tool causal discovery built for it: the network's wiring is written as a permutation of blocks times a strictly upper-triangular connection matrix, so every candidate is acyclic and executable by construction. The permutation is sampled hard in the forward pass and relaxed with a differentiable sort in the backward pass.
The payoff is a search over $n!$ execution orders that costs about as much per step as training one network. Every sampled candidate is a real, runnable feedforward network. It is never a soft mixture that cannot be executed, and it never needs a cycle penalty. The contribution has three parts: a gradient estimator that makes this cheap, a small exhaustively evaluated benchmark of block orderings that shows whether order matters at all, and a control experiment on interchangeable-node spaces where the method should provide no benefit.
Core Claim
When search nodes carry fixed operation types, the topological order of those nodes is a genuine search dimension that fixed-order supernets cannot express. It can be optimized by gradient descent at single-network cost. The wiring is parametrized as $A = \Pi^\top U \Pi$, where $\Pi$ is a permutation matrix over the $n$ typed blocks and $U$ is strictly upper-triangular. In the forward pass, $\Pi$ is a hard permutation drawn by perturbing learned per-block scores with Gumbel noise (random noise that turns an argmax into a sample) and sorting them. In the backward pass, $\Pi$ is replaced by its SoftSort relaxation.
The key observation is that the gradient signal for every possible connection comes almost for free. Each block $i$ receives the weighted sum $\sum_j A_{ij} h_j$ of other blocks' outputs $h_j$. After one hard forward pass, all $h_j$ exist, so $\partial L / \partial A_{ij} = \langle \partial L / \partial x_i, h_j \rangle$ is available for every pair $(i,j)$, including pairs the current order forbids. Here $x_i$ is block $i$'s aggregated input. This is a first-order estimate of how much the loss would change if block $j$ fed block $i$. It flows through SoftSort to the block scores at a cost of $O(n^2)$ inner products and adds no extra block evaluations.
Where This Sits in Prior Work
The parametrization comes from causal structure learning. BCD Nets factor a weighted adjacency as $P L P^\top$ and relax $P$ with Gumbel-Sinkhorn for variational inference over linear-Gaussian models. Differentiable DAG Sampling samples $\Pi^\top U \Pi$ with Gumbel-Top-k and SoftSort in a single-loop objective and reports runs of about 190 seconds on 100-node graphs. The TOBAC papers (Differentiable Bayesian Structure Learning with Acyclicity Assurance, Constraining acyclicity of differentiable Bayesian structure learning with topological ordering) use the same triangular factorization. They obtain an exactly zero cyclicity score throughout optimization, but they fix the order with heuristics. All of this work scores graphs by a likelihood over tabular variables. We reuse the parametrization and sampler, but the object being ordered is a set of neural computation blocks and the score is task loss. That change introduces a problem absent from causal discovery: a relaxed adjacency matrix cannot be executed as a network. We therefore insist on hard forward samples and derive the free all-pairs gradient above.
The relaxation operators supply the method. Gumbel-Sinkhorn networks relax permutations to doubly stochastic matrices through iterated normalization. SoftSort gives a closed-form unimodal row-stochastic relaxation of argsort. NeuralSort is an earlier variant. We default to SoftSort because it avoids unrolled iterations. The $O(n^2)$ memory cost that SoftSort's authors flag does not matter here, since $n$ counts blocks (tens), not data points.
On the search side, DARTS and GAEA relax operation choice on each edge of a fixed-order cell. Zero-Cost-PT and EZNAS score operations or networks without training. CDARTS couples search and evaluation networks; its "cyclic" refers to that training schedule, not to graph cycles. All of these assume the fixed skeleton that NAS-Bench-201 makes explicit, and Agentic Neural Architecture Search argues that such skeletons limit architectural diversity. These papers motivate the question. They also constrain it. Since NAS-Bench-201 nodes are unlabeled, our method should give nothing there, and we test that prediction rather than claiming gains on it. The DARTS memory problem, where every candidate operation is stored on every edge, is avoided because only one hard network runs per step.
Research Program
The first component is the estimator. Each block $i$ has a learned score $s_i$. At each step we draw $g_i \sim \text{Gumbel}(0,1)$ and compute the hard order $\pi = \text{argsort}(s + g)$. Connection logits on $U$ are sampled hard with a straight-through Gumbel-softmax, following Differentiable DAG Sampling. We then execute the resulting network with shared block weights, and backpropagate through $\text{SoftSort}_\tau(s+g)$ in place of $\Pi$. We will study the temperature $\tau$ and compare against Gumbel-Sinkhorn. We will also measure the bias of the first-order all-pairs gradient against finite differences, obtained by actually swapping adjacent blocks, on small $n$.
The second component is the benchmark, called OrderBench. It is needed because no benchmark in the literature we reviewed isolates ordering. We take $n=7$ distinct blocks at matched width and resolution inside one stage of a small CIFAR-10 network: 3×3 convolution, 5×5 dilated convolution, 1×1 convolution, average pooling, max pooling, a self-attention layer, and a squeeze-excitation gate. We train all $7! = 5040$ chain orderings. To keep this affordable, we follow the budgeted-estimation logic of Rethinking Performance Estimation in Neural Architecture Search. We first fully train a random subset of about 100 orderings, then pick the shortest training schedule whose Spearman correlation with full training exceeds 0.9, and use that schedule for the rest. Reduced budgets have limited ability to separate near-top candidates, so the top 50 orderings under the reduced schedule are retrained fully. A DAG variant with learned $U$ and $n$ from 12 to 16 has no exhaustive ground truth and is evaluated by retraining the discovered networks.
The third component is a control. On NAS-Bench-201, whose four intermediate nodes are interchangeable, the permutation should be pure relabeling. Adding it on top of GAEA should change neither the accuracy of the discovered architecture nor the search trajectory beyond noise.
Baselines
The naive reference point is a fixed canonical order, together with the expected accuracy of a uniformly random order. Both can be read directly from OrderBench. If the spread between the median and best ordering is within seed noise, the project stops there. The comparison that matters most is the best-found ordering's percentile relative to the distribution of all 5040.
The strongest cheap competitor is one-shot random search over orderings. We train the same shared-weight network while sampling orderings uniformly, then rank orderings by their validation loss under the shared weights and pick the top one. This isolates whether the learned scores add anything beyond weight sharing. It receives the same epochs, the same number of candidate evaluations at ranking time, and the same hyperparameter tuning budget as our method. We also run regularized evolution over orderings, using the reduced-budget training from the benchmark construction as its fitness function and giving it matched GPU hours. Following NAS-Bench-201, evolution and random search are often the methods to beat in small spaces.
The strongest training-free competitor ranks all orderings with zero-cost proxies. We use the NASWOT and Synflow proxies that EZNAS compares against. For reference, EZNAS reports a Kendall τ of 0.65 on NAS-Bench-201 CIFAR-10, against 0.57 for both NASWOT and Synflow. There is no reported result on Lacuna for any proxy on block orderings, so we report its correlation on OrderBench directly.
For the control space, the strongest existing gradient method is GAEA, which reports 94.10% CIFAR-10 accuracy on NAS-Bench-201 against an oracle of 94.37%. Matching it within noise is the expected outcome, and exceeding it is not claimed. There is no reported result on Lacuna for ordering search on any benchmark, so every OrderBench number will be new.
The key ablation replaces the SoftSort pathway with a score-function (REINFORCE) gradient for a Plackett-Luce distribution over the same Gumbel-perturbed scores, with a moving-average baseline. The sampler and forward pass stay identical, so the only difference is whether the all-pairs first-order signal is used. A second ablation swaps SoftSort for Gumbel-Sinkhorn. A third drops the permutation entirely and learns a full adjacency over typed blocks with a NOTEARS-style cycle penalty, which requires relaxed forward passes and thresholding.
We beat a baseline if, at equal GPU hours, the ordering we find sits at a higher percentile of the exhaustive OrderBench distribution across five seeds, or reaches the same percentile with less compute.
Why not just…?
Why not just keep the fixed node order that DARTS already uses? For interchangeable nodes, a fixed order loses nothing, and our NAS-Bench-201 control is designed to confirm exactly that. With typed blocks, a fixed order hard-codes one of $n!$ designs. OrderBench measures how much accuracy that costs, and if the cost is negligible we will say so and the idea fails.
Why not just enumerate orderings with shared weights, or evolve them? This is the real threat at $n=7$, where 5040 candidates are few enough to rank one by one under shared weights. We expect parity there. The claimed advantage appears as $n$ grows: at $n=12$ there are about $4.8 \times 10^8$ orderings, and enumeration or evolution samples a vanishing fraction of them, while learned scores use $n$ parameters. We will plot the found-ordering percentile against $n$ for all three methods. If random one-shot search keeps up at $n=12$ to $16$, the gradient machinery is not justified.
Why not just use score-function gradients over orderings and skip the relaxation? Plackett-Luce REINFORCE is simpler and unbiased. Its variance grows with $n!$, whereas our estimator receives information about every block pair from each forward pass. The ablation above settles this directly by comparing sample efficiency.
Why not just add a soft acyclicity penalty to a full adjacency over the blocks? The TOBAC papers and Differentiable DAG Sampling report that soft penalties leave residual cycles and require inner-outer optimization loops. For a neural network the problem is worse, because a matrix with cycles cannot be executed at all. The penalty baseline therefore needs relaxed, and in cyclic cases truncated, forward passes. We will report how often its thresholded result is cyclic and how much accuracy it loses after discretization.
Proposed Experiments and Decisive Checks
The first decisive check is whether order matters. On OrderBench, we measure the gap in fully trained CIFAR-10 accuracy between the median and best orderings across three seeds. A gap below two standard deviations of seed noise ends the project.
The second is whether gradients find good orders cheaply. We report the percentile of the found ordering, Kendall τ between the learned scores' induced ranking and the true ranking, and GPU hours, for our method against every baseline, at $n=7$ and on subsampled 5- and 6-block versions.
The third is scaling. For the DAG variant at $n$ from 12 to 16, we retrain discovered networks on CIFAR-10 and CIFAR-100 and compare them against the one-shot random, evolution, and penalty baselines at matched compute. We report peak memory to confirm single-network cost relative to a DARTS-style mixture over the same blocks.
The fourth is the control. On NAS-Bench-201, GAEA with and without a learned permutation should be indistinguishable. A significant difference would mean the permutation is acting as an optimization regularizer rather than as an expressivity gain, which would itself be worth reporting in light of the TOBAC variance-reduction findings.
Finally, gradient fidelity. On $n=7$ we correlate the first-order predicted loss change for adjacent swaps with the measured change. This shows whether the free all-pairs gradient is informative, or whether the method only works because of the Gumbel exploration.
References
- BCD Nets: Scalable Variational Approaches for Bayesian Causal Discovery
- Differentiable DAG Sampling
- Differentiable Bayesian Structure Learning with Acyclicity Assurance
- Constraining acyclicity of differentiable Bayesian structure learning with topological ordering
- Learning Latent Permutations with Gumbel-Sinkhorn Networks
- SoftSort: A Continuous Relaxation for the argsort Operator
- Stochastic Optimization of Sorting Networks via Continuous Relaxations
- DARTS: Differentiable Architecture Search
- Geometry-Aware Gradient Algorithms for Neural Architecture Search
- Zero-Cost Operation Scoring in Differentiable Architecture Search
- EZNAS: Evolving Zero-Cost Proxies For Neural Architecture Scoring
- Cyclic Differentiable Architecture Search
- NAS-Bench-201: Extending the Scope of Reproducible Neural Architecture Search
- Agentic Neural Architecture Search
- Rethinking Performance Estimation in Neural Architecture Search