MathNAS: If Blocks Have a Role in Mathematical Architecture Design
Authors: Wang Qinsi
Jinghan Ke
Zhi Liang
Sihai Zhang
Venue: NeurIPS 2023 poster (2023)
Keywords: Neural Architecture Search
TL;DR: This work introduces MathNAS, the first architecturally-general NAS framework based on mathematical programming, which reduces network search complexity from exponential to polynomial levels while maintaining excellent network performance.

Abstract: Neural Architecture Search (NAS) has emerged as a favoured method for unearthing effective neural architectures. 
Recent development of large models has intensified the demand for faster search speeds and more accurate search results. 
However, designing large models by NAS is challenging due to the dramatical increase of search space and the associated huge performance evaluation cost. 
Consider a typical modular search space widely used in NAS, in which a neural architecture consists of $m$ block nodes and a block node has $n$ alternative blocks. 
Facing the space containing $n^m$ candidate networks, existing NAS methods attempt to find the best one by searching and evaluating candidate networks directly.
Different from the general strategy that takes architecture search as a whole problem, we propose a novel divide-and-conquer strategy by making use of the modular nature of the search space.
Here, we introduce MathNAS, a general NAS framework based on mathematical programming.  
In MathNAS, the performances of all possible building blocks in the search space are calculated first, and then the performance of a network is directly predicted based on the performances of its building blocks.
Although estimating block performances involves network training, just as what happens for network performance evaluation in existing NAS methods, predicting network performance is completely training-free and thus extremely fast. In contrast to the $n^m$ candidate networks to evaluate in existing NAS methods, which requires training and a formidable computational burden, there are only $m*n$ possible blocks to handle in MathNAS.
Therefore, our approach effectively reduces the complexity of network performance evaluation. 
The superiority of MathNAS is validated on multiple large-scale CV and NLP benchmark datasets. 
Notably on ImageNet-1k, MathNAS achieves 82.5\% top-1 accuracy, 1.2\% and 0.96\% higher than Swin-T and LeViT-256, respectively. 
In addition, when deployed on mobile device, MathNAS achieves real-time search and dynamic network switching within 1s (0.4s on TX2 GPU), surpassing baseline dynamic networks in on-device performance.

MathNAS: If Blocks Have a Role in Mathematical
Architecture Design
Qinsi Wang!" Jinghan Ke
Zhi Liang" Sihai Zhang
University of Science and Technology of China School of Life Sciences, University of Science and Technology of China Communications, Chinese Academy of Sciences School of Microelectronics, University of Science and Technology of China {wqs, jinghan) @mail. ustc. edu. cn, {liangzhi, Shzzhnn)@uus @ustc. edu. cn
Key Laboratory of Wireless-Opiie
Abstract
Neural Architecture Search (NAS) has emerged as a favoured method for unearthing effective neural architectures. Recent development of large models has intensified the demand for faster search speeds and more accurate search results. However, designing large models by NAS is challenging due to the dramatical increase search space and the associated huge performance evaluation cost. Consider typical modular search space widely used in NAS, which a neural architecture consists of block nodes and block node has alternative blocks. Facing the space containing n² candidate networks, existing NAS methods attempt to find the best by searching and evaluating candidate networks directly. Different from the general strategy that takes architecture search as a whole problem, we propose novel divide-and-conquee strategy by making use of the modular nature of the search space. Here, we introduce MathNAS, a general NAS framework based on mathematical programming. In MathNAS, the performances of the m possible building blocks in the search space are calculated first, and then the performance of network is directly predicted based the performances of its building blocks. Although estimating block performances involves network training, just as what happens for network performance evaluation in existing NAS methods, predicting network performance is completely training-free and thus extremely fast. In contrast to the n candidate networks evaluate in existing NAS methods. which require training and formidable computational burden, there are only m * possible blocks handle MathNAS. Therefore, our approach effectively reduces the complexity of network performance evaluation. The superiority of MathNAS is validated on multiple large-scale CV and NLP benchmark datasets. Notably on ImageNet-lk, MathNAS achieves 82.5% top-1 accuracy, 1.2% and 0.96% higher than Swin-T and Le ViT-256, respectively. In addition, when deployed on mobile devices, MathNAS achieves real-time search and dynamic network switching within Is (0.4s on TX2 GPU), surpassing baseline dynamic networks in on-device performance. Our code is available at https://github.com www.t/ug...oo///ginniiii...ia I/MathNAS.
Introduction
Neural Architecture Search (NAS) has notably excelled in designing efficient models for Computer Vision (CV) 2 3 and Natural Language Processing (NLP) 5 6 7 tasks. With the growing
popularity of the Transformer architecture 91 designers are increasingly drawn to using NAS to
Equual contribution.
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

develop powerful large-scale models. Many existing NAS studies focus on designing search spaces for large models and conducting searches within them [O]
However, designing large models by NAS is challenging due to the dramatical increase of search space and the associated huge performance evaluation cost [10 13. Consider a widely used modular search space, in which neural architecture is treated as a topological organization of m different block nodes and each block node has n different block implementations. Obviously, the number of possible networks or neural architectures, n"", grows explosively with n. and m. In addition, candidate networks of large models are larger and require more computation for performance evaluation. Therefore, in order to conduct an effective architecture search, a proper search strategy and a suitable performance evaluation method are extremely important.
convert NAS to mathemat- ical programming (MP) problems, which substantially decrease the search cost. MP-NAS provides promising direction for rapidly designing large models. However, current MP-NAS methods exhibit certain architectural constraints. For example, DeepMAD (14) is solely applicable for architecture de- sign within CNN search spaces, and LayerNAS [15 is exclusively suitable for hierarchically ordered search spaces. These limitations impede the application of MP-NAS methods to advanced search spaces, such as SuperTrrassfomer [T3] 5] Besides, alternative strategies for effective performance evaluation of candidate networks are also expected, despite the improvement brought by parameter
It is noteworthy that to improve search strategy, recent researches 14 15
sharing [16 [7]. performance prediction based on learning curves [18 19 and so on.
In this study, we introduce MathNAS, novel MP-NAS framework for universal network architecture search. In contrast to previous studies which estimate the performance of a network by solving a whole problem, MathNAS adopts alternative dwvide-and-conuee" approach. In brief, MathNAS improves the performance evaluation of a candidate network by estimating the performance of each block of the network first, and then combining them to predict the overall performance of the network. Although estimating block performance involves network training, predicting network performance completely training-frees Therefore, this approach reduces the complexity of network performance evaluation. MathNAS achieves further improvement of the search strategy by transforming NAS to a programming problem, reducing the search complexity to polynomial time.
MathNAS contains three key steps:
Block performance estimation: The performance of each block is estimated by the perfor- mance difference between networks having and having not that specific block.
Network performance prediction: The performance of a network is predicted based on the performances of its blocks.
NAS by ILP: Utilizing the block performances, NAS is solved an Integer Linear Pro- gramming (ILP) problem.
We perform experiments on search spaces with various network architectures, including NAS-Bende 201 (GNN) (20). MobileNetV3 (CNN) (21), SuperTransformer (Transformer) (5) and NASVIT (CNN+Trans) 13 Our experiments demonstrate that predicting network performance based on its blocks' performances is applicable to different network architectures. In particular, the Spearman coefficient between the actual and the predicted top-1 indices on four different search spaces achieve 0.97, 0.92, 0.93, and 0.95, respectively. At the same time, by using the merit of the strategy to transform NAS into an II.P problem, MathNAS can find models superior to state-of tate-offtthe-ar (SOTA) models across different search spaces and tasks. In CV tasks, MathNAS achieves 82.5% top- accuracy on ImageNet- Ik with 1.5G FLOPS and 15M parameters, outperforming AutoFormer-smal (81.7%) and Le (81.6%). In NLP tasks, MathNAS reaches Blue Score of 28.8, on par with Transformer (28 4), but requiring only 1/5 of the FLOPs. In summary, our contributions are as follows:
and-conquer
1. We propose general framework for performance evaluation of candidate networks by estimating block performance first and then combining them to predict network performance, which greatly improves the evaluation efficiency.
2. By virtue of the established mapping between block performance and network performance, we transform NAS into an ILP problem, which reduces the search complexity to polynomial.
3. We demonstrate MathNAS by considering three key performance indices for network design, i.c. accuracy, latency and energy, and achieve results superior to SOTA models.

---

2 The Proposed Method
Search Space and Notations. In this paper, we consider a widely used modular search space S = [Ni,...,Nk,.... in which network Ai. consists of m block nodes (1 < i S m). For block node, there alternative blocks, i.e. B, = {bi.1; ......... Di.j..... bin) where block br, (1 S
m, S S n) represents the j-th implementation of the i-th block node. A network can therefore be denoted as N = (bi.7..... b..J.:... Pm. ). with its i-th block node implemented by block b Totally. there are m" possible networks in the search space. Here, we focus on three key performance indices for network design, i.e. aceuracy, latency and energy consumption. The accuracy, latency and energy consumption of network N are denoted as Aco(N), Lat(N), Eng(N). respectively.
2.1 Problem Formulation: Reduce NAS Search Complexity from O(n")) ) to O(m n).
The objective of hardware-aware NAS is find the best neural architecture N with the highest accuracy under limited latency L and energy consumption É in the search space S:
N arg maxAc((N)) Lat(N) s L, Eng(AV) É .NeS
(I)
In order to fulfill the above goal, NAS has to search huge space, evaluate and compare the performance of candidate networks. Early NAS studies usually fully train the candidate networks to obtain their performance ranking, which is prohibitively time-consuming. Subsequent works introduce various acceleration methods. For instance, the candidate networks can avoid training from scratch by sharing weights [66 [7]. Also, the performance of candidate network can be predicted based on the learning curve obtained from early termination of an incomplete training 18.19] Despite of these improvements, candidate network has to be trained, no matter fully or partially, to obtain a reasonable performance evaluation. And the huge number of candidate networks in the search space poses a formidable efficiency challenge.
However, the modular nature of the search space may provide us with a novel possibility. Although there are n candidate networks in the search space, they are all constructed by the n blocks. If we can evaluate the performances of the blocks by training of limited number of networks, and if we can combine these block performance indices obtain reasonable performance evaluation of networks, we can reduce the complexity of network performance evaluation from O(n")) to On m..
Guided by this idea, we reformulate the search of N from as succession of sub- problems. Each sub-probe nub-problem corresponds to the task of searching the block br.J, with the highest accuracy within the block node B, This approach notably simplifies the original problem:
N (b1.31, b2.31 .. bm. ) arg m arg m .... arg max(bb)))) bm EBm
EB
EB
(2)
s.t.
bl.s: S LL, E
b E.
where 1r4,, b1,50 bE, represent the accuracy, latency, and energy of block b,,5 respectively. @ denotes the operation of adding block to the network. With this approach, each block b,.j is searched only once and the complexity can be effectively reduced to O(n * m). However, due to the mutual influence between blocks, a unified understanding of the relationship between the performance of AV' and its constituent blocks remains elusive, posing a challenge to the application of this method.
2.2 Divide-and-Conquee
Sowwork-Block-Netwoor
Consider the switching process (((.1))((..))) signifying the selection of the i-th B in network / as it switches from 1z, dy.J, with other selected blocks remaining unchanged. Thus, any network A =
(br.31 be. ..., bm.j..) can be viewed as the outcome of the base network N = (b1,1, be......, bm.1) undergoing m sequential switching processes. Guided by this idea, we explore two aspects:
E1: Can block performance be directly calculated as with network performance?
Considering the entire search space S, let us denote the collection of networks with the selected block by as NR which comprises m-1 networks. For any network Naa, in AB. the switch- ing process Naa)-1u) signifies the selection of the i-th B in network N as it switches from b
3

---

AcCUr022 1000
Accuracyy VOGEOO
0.7
07
85
FLOPHIN)
TLOPx000
(LPPS/M
[LOPSIN)
F.OPHIN)
FLOPHIN
(a) A Acc(N(s. (i.))) vs F(W) on NAS-Bench-201 (left) and MobileNetV3 (right).
Lotency lcsoing)
Literry losemna
Erergy bossingt
Ervegy toodm))
Emargy tossmpp
Letenay
FLOPHIM)
FLOP-IM
FLOPHIMI
FLDN001
(b) (N,1 (lefty/ AEng(Ne.. (right) vs F(N) NAS- Bens--Benc-220 on edgegpu.
Figure I: The relationship between AAce(N ALat(N
A AEng(N(ar)-tto))
and F(V). We conduct experiments on two search spaces: (1) NAS- MASS-Bench-201 [20]. Graph Network. We use the accuracy obtained on ImageNet after training each network independently. We count the accuracy of all networks in the search space. (2) MobileNetv3 [21]: sequentially connected CNN network. We use the accuracy obtained by the network with shared weights. We sample blocks per block node and count the accuracies of 3125 subnetworks on the ImageNet validation set.
to ba.j. with other selected blocks remaining unchanged. In this switch, two changes occur. The first change sees the selected block in B; switching from b to b second change arises from an internal adjustment in B;, modifying its interactions with other block spaces in the net- work. These changes lead to difference in performance between Maaa and Maaa,, denote as A Acce(N(..)- ALal(N(.1)--..))) A (Bn((((.1)-05)))) By averaging performance differ- ence obtained from all n= switching processes,Niinn ((..))-6.)))
derive two key parameters:
()(Ba))())) the change in inherent capability of B,.
2. (B(.).)))).))) the change in the interactive capability of B; within S.
Accordingly, define the performances of bú.j
b AAcc (MR
(B.
(3)
Similarly, bi and b,, can be calculated employing the same methodology. The unbiased empirical validation and theoretical proof supporting this method can be found in the Appendix.
E2: How can we predict network performance using block performance?
To accurately derive the performance difference stemming from the switching process, we consider the performance difference that a particular block switch brings to different networks. We performed the identical process ((1.1) over range of networks within A/2 (f.1)- The outcome is illustrated in Figure 1, which depicts the relationship between the differences of three performances lateen energy, and accuracy- and the FLOPs of the network. Our findings reveal that, within the same switching operation, latency and energy differences maintain consistency across different networks, while accuracy differences exhibit an inverse proportionality to network's 's FLOPSs, F(W).
This finding is logical, as networks with smaller FLOPs have lower computational complexity, rendering them more susceptible block alterations. Conversely, networks with larger FLOPs exhibit higher computational complexity, making them less sensitive to individual block switching. In the Appendix, we proceed to fit the inverse relationship between accuracy difference and network FLOPs using various formulas. The results suggest that the accuracy difference is approximately inversely related the network's FLOPs. Consequently, we can posit AAco( (Ncc(N((.))) where a represents specific block's s coefficient.
1/F(N).
Based on these observations, can deduce that for any network No(.1) within the set A/Q the performance difference resulting from the switching process can be approximated as follows:
(1.1)
F(NR.
(Lat(N ss b4,, ...Eng(((n.)) Re bEg AAcc((N..) Rs 1, F(Na.)
(4)

---

E
1009
1000
2000
Xir
N0
Latencylms)
Actual topk1
0.2
6:30
0:27
Seriia Fatietit
Sample sattecss
Radiohii
30
La)Lat on NB201
(b)Energy on NB201 (c)Acc on MBV3
(d)Acc on NB201
Validation of the predictive performance of Equation 5 and the effect of sampling rate on it. The setup of the search space is the same as in Figure | The first row shows the predictive performance of Equation 5 when calculating 6,4, bf and by_ with Equation 3 The second row shows the predictive performance of Equation [ when randomly sampling the network and computing the average difference to estimate b b and b,, for the corresponding dataset.
Figure 2:
By integrating Equation and we can estimate the performance N (b1,3r 62. b mm
Lal(N) Lal(N) >n m
i=1 Uhis.
Eng(N) = Eng(NN - > 1=1 b
F(NB.20)
(5)
Acc(N) Acc(N)
1. F(NG.OO)
Proof-of-Conceye Experiment. In our examination of the predictive efficacy of Equation 5 acrrss diverse network types, as depieted in Figure 2 we observe that it accurately forecasts three perfor- mances for both sequentially connected networks and graph networks and both reight-independent and weight-shared networks, all without necessitating network training. To the best of our knowledge, our method is the first work to precisely estimate network performances using linear formula, and notably, is theoretically applicable all architectures.
2.3 Simplification: Single-sampling Strategy Instead of Full-sampling
Despite the outstanding predictive performance displayed by { its computation of loss averages proves to be costly. In this section, by employing single-sample sampling strat- egy, we effectively reduce the time complexity from (nn") to O(n m), enhancing efficiency without compromising precision.
Algorithm Math Neural Architecture Search
Stagel: Determine the Average-FI. FL.OPs Network for i=1.2....m do
Calculate the average of the FLOPs all blacks at the note, F(b,) (F(b..1)+ +.. F(bia)) (obaa)//1 Select b,,3, whose FLOPs closest to F(b.).
end Define average-FLOPs Noog (br,7 Jm. Stage2: Calculate Block Performances for i=1.2....m do
Partial Network Sampling Strategies. We begin by investigating the sample size require- ments for 5 The second row of Figure demonstratte rapid convergence of Equation 5 with notably small sample count for perfor- mance prediction. Specifically, Figure (d) reveals that mere 5% random sampling of net- works is sufficient for the prediction to converge towards optimal performance. This underscores the impressive efficacy of Equation [5] which exhibits rapid convergence with limited number of random samples.
for j=1,2..... do
2
Switch the i-th block in Naas from d.,1 to bugi
Calculate the performance difference of the net- work brought about by switching and the performance of the block b[ by D
end end Stage3: Prediction and Architecture Search Calculate three characteristics of the base net N [b1,t:...,b,. as Acc(N), Lat(N), Eng(N); For network N = [bI.s1 b2.J2..... I... }. its accu- racy, latency and energy can be estimated by Equa. [ Set required accurac/latency/eeergy limit, and solve corresponding ILP problem to obtain the architecture.
Single Network Sampling Strategy. Build- ing upon Equation g we can select an average- FLOPs network. denoted as Aoogg in the search
5

---

Spcerman: 0.9714
Spearman: 0.9187
Spearman: 0.9255
Spearman: 0,9530
predict 11115
R240
1330p
11.73
Prodict
123
1MM
100%
260
lopk11%)
Actual tapkc
Actual 10p
(a)Acc on MBv3
(b)Acc NB201
(c)Acc SuperTran
(d)Ace on SuperVi VIT
Speermen:
Speermen: 0.9552
Spcarman. 6.9256
Spearman: 9901
Prodict Latrency(in)
mredet Latonyyi)
nom auaiig Ana -umee
Prodict Latereyling
8000
AllouBa
12:00
8000
w000
208
425
Latencylms)
MAC
500
Aciual Latency(s)
Fnergylj)
1403 Actual Latency(ms)
(e)L.t on MBv3
(f)L NB201
Eg)rr on NB201
(h)Lat SuperTran
Figure 3: MathNAS algorithm verification. We conduct experiments on search space. (1)Mo- bileNetV3 (21) (2)NAS-Bench--2) [20] (3SSuperTransformer (5) (4)SuperViT [13]. For NAS-Bench- 201, we use the accuracy of each network trained individually as Acc(N). For other spaces, the validate accuracy under shared weights base net is used. We show accuracy predictions networks as well as hardware efficiency predictions on them. The calculation of b5" b and b follows Algorithm[] [ For MAS-Bench- we verify all nets and other spaces, randomly sample 1000 nets to verify the prediction effect.
these four
space with FLOPs upproximating the mean value, ensuring F (N...)) (FNN 1. This leads to: bf, ~ AEng(N (No00 (1.1))(1.)) By incorporat- ing Aavg into Equation 5 we gain the ability to calculate any network performance. Thus, we only need to verify the performance ( and (i,)) for by., resulting in an O(n m) search time complexity. The complete MathNAS algorithm is presented in Algorithm I which, in theory, can achieve accurate prediction on any network structure with polynomial search complexity.
b2, R AAco( (Na (())-((-)))) 14, s (Laa(N(.))-x...)))
Validation experiment of single-sample strategy effectiveness. We assess the efficacy of Algo- rithm [ across CNN, GCN, Transformer, and CNN+Transformer search spaces, with the outcomes displayed in Figure 3 It is evident that the Spearman correlation coefficient between predicted and actual values exceeds 0.9 for all networks. Remarkably, accuracies of 0.95 and 0.97 are attained on ViT and CNN architectures, respectively, emphasizing the algorithm's 's robustness.
2.4 MathNAS: Converting Architecture Search to ILP.
We denote b[, as the FLOPs of block bs,,, and b E {0, as the indicator of whether block b, is used in network. If block b,, is selected the implementation of block node B, in network. 6 1, otherwise O. The problem that NAS needs solve can be formulated as:
Σ
BB F(N)
max Aco(N) b0
Em
2j=1
+ b
m
m
D
s.t. Lat(N)
Σ>
6 * b
L, Eng(N)
E
* 6
E,
(6)
15
i=1 j=1
i=1
j=1
Σ
B 1 E (0. 1) v1 sism m. m
The objective is to obtain the maximum accuracy network under two constraints. First, the latency and energy cannot exceed the limit. Second, for any block node, only one block is used. Equation oli fractional objective function, it can be transformed into ILP problem by variable substitution.

---

3 Performance Evaluation
Experiments were conducted at three levels to evaluate the efficacy of MathNAS. Firstly, validated the effectiveness of MathNAS on CV tasks by conducting searches across three different search spaces. Then we employed MathNAS to design efficient architectures for NLP tasks, showcasing its remarkable generalization capabilities. Finally, we leveraged MathNAS to perform real-time searches on edge devices, considering hardware resources, and achieved exceptional on-device performance.
3.1 Experimental Setup
Search space. For CV tasks, we validate our method on three search spaces: (1) NAS-Bench-200
20
search space encompasses 15,625 architectures in DARTS- like configuration. (2) SuperViT
13 a hybrid search space that combines VIT and CNN, containing approximately 4 x 10a0 network architectures. (3) MobileNetV3 [2I] lightweight network search space comprising about 10
network architectures. For NLP tasks, we validate our approach on the SuperTransformer search space [5], which includes 10 networks within a lightweight Transformer framework.
and MobileNerV3, we adopt the training methodology employed in [16] and [22] to train the base net for 100 epochs. Subsequently, we conducted MathNAS search on the base net. As for SuperTransformer and SuperViT, we adhere the training algorithm proposed by [33 to train the base net for 100 epochs before conducting MathNAS search. The settings of hyperparameters employ the Gurobipy solver to address the ILP problem. In the SuperViT and Super Transfrrane search spaces, we impose a search time limit of 10 seconds to expedite the process. For the other search spaces, do not enforce any time constraints.
Search and training settings. For
the training are consistent with the original paper. We
The search cost of MathNAS consists of two stages: offline network pre-training that is conducted only once and online real-time search. During the offline network pre-training. MathNAS evaluates block performance once. During online searching, MathNAS is capable of multiple real-time searches based on the current hardware resource constraints. To negate the influence of variations in GPU models and versions on the pre- pre-training time, and facilitate comparisons by future researchers, we have adopted pre-trained networks provided by existing works. All mentions of search cost in the paper refer solely to the real-time search time on edge devices. We provide a detailed description of the search space, more experimental results, and visualizations of the searched architectures in the Appendix.
3.2 MathNAS for Designing Effective CV Networks
MathNAS for NAS-Bench-201. To assess the effectiveness of our method in striking a balance between accuracy and hardware efficiency, we compare networks searched by MathNAS under hardware efficiency constraints to those searched by BRP-NAS (30), which utilizes GNN predictors estimate network performance. As illustrated in Figure 4 MathNAS consistently locates networks that approach Pareto optimality in the majority of cases, whereas the employment of GNN predictors leads to suboptimal model choices. An extensive comparison between the searched architectures and SOTA models is provided in the Appendix for further insight.
Latency on FPGAIMS)
Energy FPGAII))
Latency edgeqputins)
edgeqpu/mi)
Figure 4: comparison of networks searched by MathNAS (red circles) versus those searched by
BRP-NAS (brown triangles) in the MAS-Bench-201 space. Across different devices, the networks searched by MathNAS demonstrate closer proximity to the Pareto front (yellow five-pointed stars) as compared to the networks obtained through BRP-NAS.
7

---

Model
Top-IcR)
Top-S(8)
F(M)
Param(M)
82.5
RosNet-
77.7
91.2
82.0
ReXNe
77.9
03.
MashhNAS-Ti
78.4
93.5
200
8.9
ImageNet Top- - Accuracy
LeVIT-128
78.6
94.0
BiliceenNNe-Bll
79.1
RcXNei
79.5
MathNAS- 12
79.6
94.3
325
933
ResNatY- Pk
80.0
94.3
4000
21
LeVIE-194 E5
80.0
Etficieniet
ReXNon
80.3
ResNet- 20)23
80.6
4100
25.6
FBNetv3
MathNAS-11
$1.3
95.1
BigNAS
Efficientéét
95.5
EtficeeniNt
Harmeee-Farmer
LeV
81.6
95.4
1120
18.9
OnceForAll
RcXNe:
81.6
95.7
1500
ReXNett
AutnFormet-mmin mmmll b0
81.7
05.7
5100
22.0
DeepMAD
MathNAS-TV
82.0
95.7
1101
14.4
LayerNAS
AutoFoeessbuud
95.7
(MrthNNANS
LeVIT-88-
82.6
96.0
MathNAS-13
82.5
95.8
14.
250
03
FLOPs(M)
10:11 1220
Figure 5: MathNAS v.s. SOTA ViT and CNN models on ImageNet-
MathNAS for VIT. To assess the performance of MathNAS in designing larger models, we utilize to create effective VIT models for ImageNet-1K classification. Figure [iguureajdemonstraal that MathNAS surpasses or matches the performance of existing SOTA models. For instance, MathNAS-TS achieves an accuracy of 82.5%, which is comparable to LeViT-384 [25] and Autoformer-base [29], while consuming only about 50% and 15% of their respective FLOPs. Similarly, MathNAS- T3 achieves comparable accuracy to RexNet [24] but with approximately half the FLOPs. MathNAS also exhibits exceptional performance in the realm of small networks. Particularly, MathNAS-T achieves a top-1
accuracy of 78.4%, surpassing ResNet-
23 and ReXNet 24 by 0.7% and 0.5% respectively.
MathNAS for Mobile CNNs. We employ MathNAS to design mobile CNN models for fur- ther investigation, conducting our search within the MobileNetV3 search space. As demon- strated in Table D MathNAS-MB4 achieves a top-1 accuracy of 79.2% which is on par
Table I: Performance of mobile networks designed with MathNAS. Top-1 accuracy on ImageNet- K.
Model
FLOPsMi
Top-
Seurch Time
Scale Up
FBNes-b
AtoeNAA
74.6
192h
OFA
301
74.6
120B
9.6x
MataNAS-MB1
257
75,9
0.9g
4.6M
with EfficientNet-Bl (79. 1)). It is important note that EfficientNet-Bl derived through brute-force grid search, necessitating approx- imately 72,000 GPU hours [4. Despite this, MathNAS-MB4 offers comparable performance to EfficientNet-BB while only requiring 0.8 sec- onds to solve ILP problem the GPU and search for a suitable network. MathNAS also ex- cels in the context of smaller networks. Notably, MathNA.S- requires only 257M FLOPs to
MansNet-A |
75.2
40025h
10xx
ProxylessNSS-R NA--sNAA-RR
320
74.6
520h
76.9%
AtomNAS B
326
75.5
492h
$1.4%
FaiNAS [3
321
71.1
38th
104.2X
Single
OFA
75.8
MathNAS-MB2
76.4
12ss
144M
EdicientNet
FBNet-
74.9
124.1
465
75.
51Ah
130 5%
AtomNAS C
363
76.3
492h
146.3x
FairAAS-A 35
388
75.3
38th
104.2X
FairNAS-B 13
MaB
173MX
achieve a t accuracy of 75.9%. surpassing the performance of FBNet-b [31]. AtomNAS-A 32], and OFA 22], all of which demand higher computational resources.
EdicientNet
79,
72000
10x
MiaNNeAl
RigNAS-M
78.9
MathNAS-MBA
669
79.2
0.8
324Mx
3.3 MathNAS for Designing Effective NLP Networks
We perform a comparative evaluation of MathNAS against SOTA NLP models on the WMT' 14 En-De task to gauge its effectiveness. Table reveals that MathNAS surpasses all baseline models in terms BLEU score while also achieving FL.PPs reduction across three distinct devices. Specifically, on Intel Xeon CPUs, MathNAS with full precision attains remarkable 74% reduction in FL.OPs compared to Transformer and 23% reduction compared to HAT (5), while registering improved BLEU scores by 0.4 and 0.3, respectively, Additionally, MathNAS excels in designing lightweight

---

Table 2: MathNAS vs. SOTA baselines in terms of accuracy and efficiency on NLP tasks,
Raspherry
Intel Xeon CPU
Nvidia TITAN Xp GPU
Search Cost
Model
FL.OPs
BLEU
Latency
FL.OPs
BLEU
1 Latency
FL.OPs
BLEU
Latency
Time
CO2
Transformer g
10.6G
28.4
20.5s
10.6G
28.4
808ms
10.6G
28.4
334ms
184h
521bs
Evolved Trans. 38
2.9G
28.2
7.6s
2.9G
28.2
300ms
2.9G
28.2
124ms
219200h
624000lbs
HAT
1.5G
25.8
3.5s
1.9G
25.8
138ms
1.9G
25.6
57mu
200h
571bs
MathNAS
1.7G
25.5
3.2s
1.8G
25.9
136ms
1.8G
25.9
68ms
10s
0.0008lbs
HAT
2.3G
27.8
5.0s
2.5G
27.9
279ms
2.5G
27.9
126ms
200h
571hs
MathNAS
2.1G
28.3
4.7s
2.4G
28.6
272ms
2.0G
28.1
107ms
10s
0.0008ibs
HAT
3.0G
28.4
7.0s
3.5G
28.5
38-4ms
3.1G
28.5
208ms
200h
57lbs
MathNAS
2.8G
28.6
6.5%
2.8G
28.8
336ms
2.6G
28.6
189ms
10s
0.00081bs
NLP models. On Nvidia TITAN Xp GPUs under latency constraints, MathNAS yields FLOPs comparable HAT [5) but with a 0.3 higher BLEU score. noteworthy aspect is that the network search process facilitated by MathNAS requires only 10 seconds, considerably reducing search time. As result, employing MathNAS leads reduction of over 99% in CO2 emissions compared to baseline models, underscoring its positive environmental impact.
3.4 MathNAS for Designing Dynamic Networks.
Deployed on edge devices (Raspberry Pi 4b, Jetson TX2 CPU, TX2 GPU), MathNAS allows dynamic network switching suited to device conditions. Within the MobileNetV3 search space, account for memory limitations by calculating performance indices for each block, subsequently deploying five selected Pareto-optimal blocks balancing accuracy and latency in each block node. During runtime, latency is continuously monitored. Should surpass a preset threshold, MathNAS immediately updates the blocks' latency. Then the device solves the IIP problem to identify the optimal network architecture, comparing and switching blocks with the searched network as required.
In comparison with SOTA dynamic network models, MathNAS demonstrates superior performance as outlined in Table 3 and Figure Impressively, MathNAS solves the ILP problem on-device in a mere 0.4 seconds on the TX2 GPU, enabling real-time search. This notably enhances the number of executable networks on the device, outdoing SlimmableNet (39] and USlimmableNet [40] by factors of 781 and 116 respectively. Additionally, through block-based approach, MathNAS enables efficient network alterations by replacing only essential blocks. When compared to Dynamic- -FF [41], which shares similar performance, MathNAS significantly reduces the switching time by 80%. The Appendix details the use of Pareto-optimal blocks and related network experiment results.
Table 3: MathNAS vs. SOTA baselines in terms of Dynamic Networks.
Network
Latency (ms)
On Device Porformance
Top-1 (%)
FLOPs (M)
Raspb Pi
TX2
TX2 GPU
Seurch Method
Search
Switch
Switch
Nets
Scale Up
Model
CPU
Time
Unit
Time
Number
S-M
3D
70.5
301
1346
958
118
Manual Design
Channel
15ms
1.0x
US. MhNettNi
71.5
300
1358
959
158
Manual Design
Channel
18ms
27
6.7x
AS MNASNeN 42
75.4
532
2097
1457
2097
Greedy Slimming
400%
Channel
37ms
1.0x
Dynamic-OFA.R
78.1
752
2404
1485
80
Kandon+Eivplution
35h
Network
244ms
7.
1.7x
75.9
257
832
525
MathNAS
79.2
669
2253
1398
81
On-Device Search
0,4-12s
Block
61ms
3125
781x
Raspberry Pi
Jetson TX2 CPU
Jetson GPU
D. D.O
Accuraryts)
Accuncyy
nocuracyttu
Autoškin
20
(S-dir Ma.2
(8. gin May
Aspodi Noudli
Qurs
1.2x 20
52
400
1050
1950
2003
7500
500
750
1250
1500
Networta Search Time (eggheuee
Subewts
Latencylnn]
Latencyims)
Latencylma)
Figure 6: Top-1 vs. Latency of MathNAS over SOTA dynamic baselines on three devices.
9

---

4 Conclusion
This paper introduces MathNAS, the first archifecturally-general MP-NAS. By virtue of the modular nature of the search space, we introduce block performance and establish the mapping from block performance and network performance, which enables subsequent transformation of NAS an ILP problem. This novel strategy reduces network search complexity from exponential to polynomial levels while maintaining excellent network performance. We propose three transformation formulas to depict this process and support them with theoretical proof' and extensive experiments. Math- NAS achieves SOTA performance on various large-scale CV and NLP benchmark datasets. When deployed mobile devices, MathNAS enables real-time search and dynamic networks, surpassing baseline dynamic networks in on-device performance. Capable of conducting rapid searches on any architecture, MathNAS offers an appealing strategy for expediting the design process of large models, providing clearer and more effective solution.
Acknowledgment
We thank the anonymous reviewers for their constructive comments. This work was partially supported by National Key R&D Program of China (2022YF82902302, Sihai Zhang gratefully acknowledges the support of Innovative Research (CXCCTЕC220001),
References
[1] Minghao Chen, Houwen Peng, Jianlong Fu, and Haibin Ling, Autoformer: Searching trans- formers for visual recognition. In Proceedings of the IEEE/CVF international conference on computer vision, pages 12270-12280, 2021.
[2] Xiaoliang Dai, Alvin Wan, Peizhao Zhang, Bichen Wu, Zijian He, Zhen Wei, Kan Chen, Yuandong Tian, Matthew Yu, Peter Vajda, et al. Fbnetv3: Joint architecture-recipp search using predictor pretraining. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 16276-16285, 2021.
[3] Bichen Wu, Chaojian Li, Hang Zhang, Xiaoliang Dai, Peizhao Zhang, Matthew Yu, Jialiang Wang, Yingyan Lin, and Peter Vajda. Fbnetv5: Neural architecture search for multiple tasks in one run. arXiv preprint arXiv:2111.1000 2021.
[4] Mingxing Tan and Quoc Le. Efficientnet: Rethinking model scaling for convolutional neural networks. International conference on machine learning, pages 6105-6114 14. PMLR, 2019.
[5] Hanrui Wang, Zhanghao Wu, Zhijian Liu, Han Cai, Ligeng Zhu, Chuang Gan, and Song Han. Hat: Hardware-awant transformers for efficient natural language processing. arXiv preprint arXiv:2005. 14187, 2020.
[6] Nikita Klyuchnikov, Ilya Trofimov, Ekaterina Artemova, Mikhail Salnikov, Maxim Fedorov, Alexander Filippov, and Evgeny Burnaev. Nas- las-bench-nlp: neural architecture search benchmark for natural language processing. IEEE Access, 457477, 2022.
[7] Hung-yi Lee, Shang- Wen Li, and Ngoc Thang Vu. Meta learning for natural language processing: A survey, arXiv preprint arXiv:2205.01500 2022.
[8] Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Eukasz Kaiser, and Illia Polosukhin. Attention is all you need. Advances in neural information processing systems, 30, 2017.
[9] Salman Khan, Muzammal Naseer, Munawar Hayat, Syed Waqas Zamir, Fahad Shahbaz Khan, and Mubarak Shah. Transformers in vision: A survey. ACM computing surveys (CSUR), 54(10s): 2022.
[10] Mojan Javaheripi, Gustavo de Rosa, Subhabrata Mukherjee, Shital Shah, Tomasz Religa, Caio Cesar Teodoro Mendes, Sebastien Bubeck, Farinaz Koushanfar, and Debadeepta Dey. Literransformersearchh: Training-fres neural architecture search for efficient language models. Advances in Neural Information Processing Systems, 35:24254-24261 2022.
10

---

[11] Gresa Shala, Thomas Elsken, Frank Hutter. and Josif Grabocka. Transfer nas with meta- learned bayesian surrogates. In Sixth Workshop on Meta-Learning the Conference on Neural Information Processing Systems.
[12] Zihao Sun, Yu Hu, Shun Lu, Longxing Yang, Jilin Mei, Yinhe Han, and Xiaowei Li. Agnas: Attention-guided micro and macro-architecture search. In International Conference on Machine Learning, pages 20777-20789. PMIR, 2022.
[13] Chengyue Gong, Dilin Wang, Meng Li, Xinlei Chen, Zhicheng Yan, Yuandong Tian, Vikas Chandra, et al. Nasvit: Neural architecture search for efficient vision transformers with gradient conflict aware supernet training. In International Conference Learning Representations, 2021.
[14] Xuan Shen, Yaohua Wang. Ming Lin, Yilun Huang, Hao Tang, Xiuyu Sun, and Yanzhi Wang. Deepmad: Mathematical architecture design for deep convolutional neural network. arXiv preprint arXiv:2303.02165; 2023.
[15] Yicheng Fan, Dana Alon, Jingyue Shen, Daiyi Peng, Keshav Kumar, Yun Long, Xin Wang, Fotis Iliopoulos, Da- Da-Cheng Juan, and Erik Vee. Layernas: Neural architecture search in polynomial complexity. arXiv preprint arXiv:2304. 11513 2023.
[16] Hieu Pham, Melody Guan, Barret Zoph, Quoc Le, and Jeff Dean. Efficient neural architecture search via parameters sharing. In International conference on machine learning, pages 4095- 4104. PMLR, 2018.
[17] Andrew Brock, Theodore Lim, James M Ritchie, and Nick Weston. Smash: one-shot model architecture search through hypernetwrrs.. arXiv preprint arXiv:1708.05344, 2017.
[18] Bowen Baker, Otkrist Gupta, Ramesh Raskar, and Nikhil Naik. Accelerating neural architecture search using performance prediction. arXiv preprint arXiv: 1082, 2017.
[19] Boyang Deng, Junjie Yan, and Dahua Lin. Peephole: Predicting network performance before training. arXiv preprini 1712:0171..03311 2017.
[20] Xuanyi Dong and Yi Yang. Nas-bench-201: Extending the scope of reproducible neural architecture search. arXiv preprint arXiv:2001.00326, 2020.
[21] Andrew Howard, Mark Sandler, Grace Chu, Liang-Chieh Chen, Bo Chen, Mingxing Tan, Weijun Wang, Yukun Zhu, Ruoming Pang, Vijay Vasudevan, al. Searching for mobilenetv3, In Proceedings of the IEEE/CVF international conference on computer vision, pages 1314-1324, 2019.
[22] Han Cai, Chuang Gan, Tianzhe Wang, Zhekai Zhang, and Song Han. Once-for all: Train one network and specialize for efficient deployment. arXiv preprint arXiv: 09791, 2019.
[23] Sasha Targ, Diogo Almeida, and Kevin Lyman. Resnet in resnet: Generalizing residual architectures. arXiv preprint arXiv:1603.cm 08009, 2016.
[24] Dongyoon Han, Sangdoo Yun, Byeongho Heo, and YoungJoon Yoo. Rethinking channel dimensions for efficient model design. In Proceedings the IEEE/CVF conference on Computer Vision and Pattern Recognition, pages 732-741, 2021.
[25] Benjamin Graham, Alaaeldin El-Nouby, Hugo Touvron, Pierre Stock, Armand Joulin, Hervé Jégou, and Matthijs Douze. Levit: a vision transformer in convnet's 's clothing for faster inference. In Proceedings of the IEEF/CVF international conference on computer vision, pages 12259-
1 12269, 2021.
[26] Mingxing Tan and Quoc Le. Efficientnet: Rethinking model scaling for convolutional neural networks, May 2019.
[27] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition, Dec 2015.
11

---

[28] Ze Liu, Yutong Lin, Yue Cao, Han Hu, Yixuan Wei, Zheng Zhang, Stephen Lin, and Baining Guo. Swin transformer: Hierarchical vision transformer using shifted windows. In 2021 IEEF/CVF International Conference on Computer Vision (ICCV), Mar 2022.
[29] Minghao Chen, Houwen Peng. Jianlong Fu, and Haibin Ling, Autoformer: Searching trans- formers for visual recognition, Jul 2021.
[30] Lukasz Dudziak, Thomas Chau, Mohamed Abdelfattah, Royson Lee, Hyeji Kim, and Nicholas Lane. Brp-nas: Prediction- based nas using gens. Advances in Neural Information Processing Systems, 33: 13:10480-10490, 2020.
[31] Bichen Wu, Xiaoliang Dai, Peizhao Zhang, Yanghan Wang, Fei Sun, Yiming Wu, Yuandong Tian, Peter Vajda, Yangqing Jia, and Kurt Keutzer. Fbnet: Hardware-aware efficient convnet design via differentiable neural architecture search. In Proceedings of the IEEE/CVF Conference 2019.
on Computer Vision and Pattern Recognition, pages
[32] Jieru Mei, Yingwei Li, Xiaochen Lian, Xiaojie Jin, Linjie Yang, Alan Yuille, and Jianchao Yang. Atomnas: Fine-grained end-to-end neural architecture search. arXiv preprint 19Xiv:9112.960 2019.
[33] Mingxing Tan, Bo Chen, Ruoming Pang, Vijay Vasudevan, Mark Sandler, Andrew Howard, and Quoe V Le. Mnasnet: Platform-aware neural architecture search for mobile. In Proceedings of the IEEE/CVF conference on computer vision and pattern recognition, pages 2228, 2019.
[34] Han Cai, Ligeng Zhu, and Song Han. Proxylessnas: Direct neural architecture search on target task and hardware. arXiv preprint arXiv:1812.0033 2018.
[35] Xiangxiang Chu, Bo Zhang, and Ruijun Xu. Fairas:: Rethinking evaluation faimess of weight sharing neural architecture search. In Proceedings of the IEEE/CVF International Conference on computer vision, pages 12239-12248, 2021.
[36] Zichao Guo, Xiangyu Zhang, Haoyuan Mu, Wen Heng, Zechun Liu, Yichen Wei, and Jian Sun. Single path ohe-shot neural architecture search with uniform sampling. In Computer Vision- ECCV 2020: 16th European Conference, Glasgow, UK, August 23-28, 2020, Proceedings, Part XVI 16, pages 544-560. Springer, 2020.
[37] Jiahui Yu, Pengchong Jin, Hanxiao Liu, Gabriel Bender, Pieter-Jan Kindermans, Mingxing Tan, Thomas Huang, Xiaodan Song, Ruoming Pang, and Quoc Le. Bignas: Scaling up neural architecture search with big single-stage models. In Computer Vision-ECCV 2020: 16th European Conference, Glasgow, UK. August 28-28, 2020, Proceedings. Part VII 16, pages 702-717. Springer, 2020.
[38] David So, Quoe Le, and Chen Liang. The evolved transformer. In International conference on machine learning, pages 5877-5886. PMLR, 2019.
[39] Changlin Li, Guangrun Wang, Bing Wang, Xiaodan Liang, Zhihui Li, and Xiaojun Chang. Dynamic slimmable network. Proceedings of the IEEE/CVF Conference on computer vision and pattern recognition, pages 8607-8617, 2021.
[40] Jiahui Yu and Thomas S Huang. Universally slimmable networks and improved training techniques. In Proceedings of the IEEE/CVÉ international conference on computer vision, pages 1803-1811, 2019.
[41] Wei Lou, Lei Xun, Amin Sabet, Jia Bi, Jonathon Hare, and Geoff V Merrett. Dynamic-ofa: Runtime dnn architecture switching for performance scaling on heterogeneous embedded platforms. Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 3110-3118, 2021.
[42] Jiahui Yu and Thomas Huang. Autoslim: Towards one-shot architecture search for channel numbers. arXiv preprint arXiv: 2019.
12


Reviews:
[{"review_id": "F01QIsAsHw", "reviewer": "Reviewer_3m52", "summary": "This paper presents a divide-and-conquer neural architecture search methodology that estimates DNN performance based on the individual performance of each block within a DNN. Accuracy is estimated based on the perturbed accuracy of replacing a block within the NN, and latency/energy are also used within a linear model to predict NN characteristics.", "questions": "see above", "limitations": "see above", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The paper is generally well-written and the results are strong compared to the chosen baselines from both CNNs and transformer based vision models. The efficacy of the method on 4 search spaces is impressive.", "weaknesses": "There are 3 main weeknesses / questions that I have regarding the paper:\n\n1. As a blockwise NAS approach, this paper largely ignores much of the prior literature on the topic, for example, [1,2,3]. These prior works also rely on blockwise layer statistics (sometimes obtained through distillation) then the layerwise performance is assembled either with a learned predictor [1,2] or ILP [3] similar to what is proposed in this work.\n2. A large part of the evaluation is done on NB201 which isn't a macro search space. I am a bit confused as to how that evaluation on NB201 demonstrates the presented blockwise methodology -- all blocks within NB201 are identical, just sized differently. Perhaps this is something the authors can clarify in the rebuttal? I understand that the plots in Fig. 1 are showing the accuracy delta when one block is replaced with another, bit this would switch out the entire network basically, right?\n3. Some conclusions (e.g. line 156) may be too specific to NB201. The inverse correlation of flops and accuracy is not a hard rule and many counterexamples can be presented. On NB201 specifically, it is widely known that this holds.\n4. Search cost is written as \"10 minutes\" does this include all the time to evaluate individual blocks and build up the model? I think this cost should be quantified clearly in the paper.\n\n\n[1] Distilling Optimal Neural Networks: Rapid Search in Diverse Spaces\n[2] Blockwisely Supervised Neural Architecture Search with Knowledge Distillation\n[3] LANA: Latency Aware Network Acceleration\n[4] BLOX: Macro Neural Architecture Search Benchmark and Algorithms", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your thoughtful review of our work. \n\n---\n# Citations\nWe have meticulously reviewed the mentioned works and discussed the distinctions between MathNAS and them in the *common response*. Furthermore, we compared the accuracy prediction performance of MathNAS with these works. The experimental results can be found in the *rebuttal pdf*.\n\n---\n# Experiments on NAS-Bench-201\nFirst, let's clarify the specific application of MathNAS in the NAS-Bench-201 search space. As you rightly pointed out, NAS-Bench-201 is not a macro search space, and during a block switch, all blocks undergo changes. In this paper, the \"block\" concept we mentioned in the paper corresponds to the \"edge operations\" in NAS-Bench-201. Consequently, in Figure 1, the block switch operation within this space refers to the delta accuracy resulting from a change in one edge operation while keeping other edge operations constant. This is consistent with the essential nature of switching in MathNAS.\n\nIn the paper, since we also considered macro search spaces beyond NAS-Bench-201, we adopted the \"block\" concept for modeling and derivation for the sake of uniform representation. NAS-Bench-201 can be viewed as a special case of the MathNAS model. \n\nIn the revised version, we will elaborate and clarify this matter further.\n\n---\n# Generality of Conclusions\nWe concur with your observation that conclusions drawn from prior works in the NAS field concerning NAS-Bench-201 may not necessarily hold in other search spaces. However, we believe our experiments demonstrate the generalizability of the proposed rule from two aspects:\n- First, we validated the inverse proportionality rule between delta-Accuracy and FLOPs on both MobileNetV3 and NAS-Bench-201, as depicted in Figure 1 of the paper. MobileNetV3, being a macro search space constructed from sequentially connected inverted residual blocks, contrasts starkly with NAS-Bench-201. The verification in the MobileNetV3 search space underscores the universal applicability of the stated rule across diverse architectures.\n- Second, we tested the network performance prediction formula derived from the inverse relationship between FLOPs and delta-Accuracy (i.e., Equation 5) across four distinct search spaces: NAS-Bench-201, MobileNetV3, SuperViT, and SuperTransformer, as showcased in Figure 3 of the paper. These spaces encompass varied network architectures (detailed descriptions of search space structures can be found in Appendix D.1), including CNN, GCN, and Transformer, representing the majority of contemporary NAS search space architectures. Hence, the validation across these four spaces suggests that the introduced inverse rule and the network performance prediction formula can be applied broadly across most search spaces.\n\nGiven the above, we feel that the statement, \"A large part of the evaluation is done on NB201,\" doesn't quite align with our experimental setup. We referenced NAS-Bench-201 more frequently in our paper because it offers detailed and reliable performance information for its contained architectures, which might have inadvertently led to misunderstandings.\n\n---\n# Search Cost\nAfter a thorough review, we couldn't locate any mention of a \"10 minutes\" search cost. Perhaps you are referring to the \"10 seconds\" mentioned in Table 1.\n\nIn the *common response*, we provided an explanation of the search cost. In the revised version, we will provide a clearer elucidation of this aspect."}, {"review_id": "PXWpirV5AJ", "reviewer": "Reviewer_8XzK", "summary": "This paper introduces MathNAS, a blockwise NAS framework. It begins by estimating the performance of the building blocks within the search space and then predicts the overall performance of a network based on the performance of its individual building blocks. This approach effectively reduces the complexity of network search from O(n^m) to O(nm). Additionally, a block performance evaluation scheme, utilizing average FLOPs, is proposed to further reduce the time complexity from O(n^m) to O(nm). Lastly, the network search process is formulated as an Integer Linear Programming (ILP) problem.", "questions": "* Figure 1 in the appendix requires clarification. It appears to suggest the presence of three levels of blocks, with each level accommodating parallel blocks. Could you please clarify whether the blocks are connected sequentially or in parallel? Additionally, how many levels of blocks are there?\n\n* In Algorithm 1, there is an inconsistency with the existence of b_{i,0}, which does not align with the range specified for i (i={1, m}). Is this a typographical error?\n\n* Regarding the results on NB-201, it would be beneficial to know if multiple runs were performed to obtain averages using different seeds. Similarly, for the Mobile CNN, ViT, and NLP networks, were multiple runs conducted to calculate the means and variances?\n", "limitations": "The paper does not explicitly mention the limitations and potential negative social impact of their work.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "* Clarity: The paper is effectively written, employing appropriate mathematical notations throughout.\n\n* Quality: The experiments conducted in the paper are of high quality, as they include a comprehensive comparison with well-known networks in various domains, such as tabular search space, mobile CNN, ViT, and NLP.\n\n* Originality and significance: While the paper presents valuable contributions, there are some concerns that should be addressed. Please refer to the weaknesses section outlined below.", "weaknesses": "The paper does not cite a few highly relevant papers on blockwise NAS.\n* LANA: Latency Aware Network Acceleration. https://arxiv.org/pdf/2107.10624.pdf\n* Distilling Optimal Neural Networks: Rapid Search in Diverse Spaces. https://arxiv.org/pdf/2012.08859.pdf\n* BLOX: Macro Neural Architecture Search Benchmark and Algorithms. https://arxiv.org/pdf/2210.07271.pdf\n\nThe authors should thoroughly discuss the distinctions between their proposed approach and the previously mentioned works, while also considering the possibility of conducting experiments to compare them. Specifically, LANA adopts a constrained ILP approach that relies on block metrics derived from factors such as delta-accuracy and delta-latency. The proposed approach bears resemblance to LANA.\n\nWhile the authors have made an effort to explain the validity of their approach, as depicted in Figure 1 and Section C of the appendix, it remains unconvincing that Equation 2 holds true under all circumstances. Additionally, Equations 3 and 4 are similar to those presented in LANA.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your thoughtful review of our work. \n\n---\n# Originality and Contribution\n#### Regarding the comparison of the effectiveness of MathNAS and blockwise methods, we responded in the *common response*. At the same time, we supplemented the experimental comparison between MathNAS and the block-wise methods, refer to *rebuttle PDF*.\nHere we mainly clarify the difference between our work and LANA.\n\n### Block Performance Evaluation\n\n**LANA** switches blocks on the teacher net (typically the largest network within the search space) and directly uses the resultant accuracy change as the block's performance metric.\n\n**MathNAS** conducts block switches on a network whose FLOPs represent the average within the search space. This particular network is chosen based on the observed inverse relationship between FLOPs and delta-Accuracy. We estimate block performance using the accuracy changes observed on this network. Experimental results indicate that this is a more efficient and accurate method for evaluating block performance.\n\n### Network Accuracy Evaluation\n\n**LANA** estimates network performance by simply summing up the block performance. It assumes that the impact of a specific block switch remains consistent across different architectures.\n\n**MathNAS** employs a weighted evaluation of block performances based on the network's FLOPs, thereby offering a more precise assessment of each block's influence on overall network accuracy. This method subsequently aids in more accurate network performance predictions. Furthermore, both theoretically and empirically, we've demonstrated that the effects of a specific block switch vary across different architectures. While exploring these variances, we suggest that the influence of block performance on network accuracy can be explored from two perspectives: inherent capability and interactive capability.\n\n### Network Latency/Energy Consumption Evaluation\n\n**LANA** estimates network latency by summing up block latencies, which restricts LANA's prediction method to be suitable only for macro search spaces with sequential block connections.\n\n**MathNAS** calculates the delta-Latency for each block based on the obtained block latency. It considers the network latency to be equal to the difference between the latency of the initial architecture and the delta-latency of each block comprising the network. This makes our latency prediction method applicable to micro search spaces, such as NAS-Bench-201.\n\n#### LANA and MathNAS both employ the concept of delta-Accuracy for estimating network performance. This similarity might lead one to believe that Equations 3 and 4 in MathNAS resemble those in LANA. However, it's crucial to note that the block performance evaluation method and the network performance prediction formula in MathNAS are fundamentally distinct from those in LANA.\n\n---\n# Other Questions\n\n## Figure 1 in the appendix:\n\n**In fact, this figure does not represent a specific search space.** Our intention is to demonstrate the architectural versatility of MathNAS, that is, it can be applied to search spaces where the block structure is serial or parallel. Specifically, we used four classic search spaces during the experiment: NASBench201, MobileNetV3, Supervit and Supertransformer. A detailed description of their architecture is in Appendix D.1. We are aware of the possible misinterpretations that our diagrams can cause. In the latest revised version, we will remove this figure.\n\n##  Typographical error in Algorithm 1:\n\nThank you for your meticulous review. Indeed, **this is a typographical error**. In the revised version, we will make the necessary correction.\n\n## Obtain averages using different seeds:\n\nGiven that the essence of our search algorithm is to solve an ILP (Integer Linear Programming) equation, we employed the Gurobipy and Linprog libraries in Python for the solution. Within a fixed time frame, the solution obtained by the solver is unique and deterministic; hence, **there was no need for multiple computations to obtain average values and variance** in our experiments. Details on solving the ILP equation can be found in the \"common response\" section.\n\n## Limitations and negative social impact discussion:\n\nIn the revised article, we will add a discussion of the limitations of our work and potential negative societal impacts. Here we give a brief overview of it:\n\n### limitations and future work:\n- The theoretical explanation of the law of FLOPs and accuracy changes proposed by MathNAS needs to be strengthened. We intend to continue to explore and try to give a complete theoretical proof from the aspect of network interpretability.\n- Zero-shot NAS algorithms have been proven to be more efficient. Our future goal is to investigate the potential of applying MathNAS to zero-shot NAS algorithms.\n\n### Potential negative societal impact:\n\nOur proposed technique for rapidly designing network architectures may lead to unemployment of network architecture designers. The technology can also be misused by those who might create evil artificial intelligence."}, {"review_id": "rLsWLqHyor", "reviewer": "Reviewer_qYEV", "summary": "This paper introduces MathNAS, a mathematical programming NAS algorithm. MathNAS maps network performance to block performance, enabling the prediction of accuracy, latency, and energy consumption of large networks based on their constituent modules. This algorithm reduces the search space from n^m to m*n, allowing the NAS problem to be solved as an Integer Linear Programming problem.", "questions": "In all the experiments, MathNAS takes significantly less \"search time\" than the other methods, especially some methods need thousands of hours while MathNAS only requires several seconds, which is very impressive. Is the time for all the other methods include the model training time (either training time of supernet or the subnet)? If yes, for the fair comparison, for the MathNAS, should the time that needed to train the base model be added to this time as well? Also, as algorithm 1 shows that there are three steps for MathNAS to determine the best architecture, should the time that calculate each block's performance also be added to the total \"search time\"?", "limitations": "N/A", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "Overall, this paper is well-written and organized, making it easy to follow along. The authors did a great job explaining their methods in detail, complete with loads of equations and clear explanations. Plus, the proposed algorithm has undergone numerous experiments under different models and application fields, which consistently showcase its effectiveness.", "weaknesses": "1)\tIn all the experiments, MathNAS takes significantly less \"search time\" than the other methods, especially some methods need thousands of hours while MathNAS only requires several seconds, which is very impressive. Is the time for all the other methods include the model training time (either training time of supernet or the subnet)? If yes, for the fair comparison, for the MathNAS, should the time that needed to train the base model be added to this time as well? Also, as algorithm 1 shows that there are three steps for MathNAS to determine the best architecture, should the time that calculate each block's performance also be added to the total \"search time\"?\n\n2)\tThe order of the tables and the description of the experimental results in the paper do not follow the same order. For example, the text follows GNN -> CNNs (Table 2) -> ViT -> NLP (Table 1) -> Dynamic Networks (Table 3), which leads is hard to follow.\n\n3)\tA typo in paragraph \"MathNAS for Mobile CNNs ...\", the top-1 accuracy of MathNAS-MB1 is 75.9% as shown in the table, not 76.4%.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your thoughtful review of our work. Here we respond point-to-point to your questions.\n\n---\n# Search Time\nWe explain the search times mentioned in the paper in the *common response*. \n\nTo ensure a fair comparison, as you rightly pointed out, we will include the training time for the MathNAS base model in the revised version.\n\n---\n# Description Order\nWe are aware of this issue and will address and rectify it in the revised version. We sincerely apologize for any inconvenience caused during your reading.\n\n---\n# Misspell\nOnce again, we greatly appreciate your patient and meticulous review. \n\nIndeed, this oversight was our mistake. We have rechecked the number and will incorporate the necessary corrections during our revision. \n\nAccurate data presentation is vital for the advancement of NAS research. To ensure our data is correctly represented, we have reviewed all other data points in addition to the ones you highlighted."}, {"review_id": "UEoIkc7qRq", "reviewer": "Reviewer_HYbp", "summary": "The paper proposes a way to perform neural architecture search (NAS) by solving an integer program to identify the constituents of a block-modular neural net, having pre-computed estimations of performance for the separate blocks by a novel method. The resulting \"MathNAS\" approach is demonstrated in various experiments to be able to yield competitive neural network designs compared to other state of the art NAS methods.\n\n-- update: I have read and acknowledged all other reviews and the authors rebuttals, see discussion. --", "questions": "- what exactly do you mean by \"polynomial-time search complexity\"? It is quite confusing to read something like \"...can be transformed into an integer programming problem, which further reduces the search complexity to polynomial time\" -- solving IPs is generally not possible in polynomial time!   I suspect the authors mean that they need to pre-compute polynomially many values (for their performance estimation scheme), but this does not really become clear.\n- In the same vein, it is mentioned that some neural network training is necessary, but it is never clearly stated what and when. Again, I guess training is required to pre-compute the block performance scores somehow, but the details of this are too vague; this certainly needs to be clarified.\n- Could you describe a bit more how flexible the block/modular architecture is? (i.e., mention earlier that blocks can be construed of essentially any (finite) number of sub-network; this is never clearly stated and only becomes more clearly apparent in the supplementary document where details on the search spaces in the different experiments are given).\n- You claim at several points that the integer programs were solved with Gurobi (that is the solver name; Gurobipy is merely its Python interface...) on a GPU.  I am quite sure that Gurobi does not run on GPUs. MIP solvers currently do not benefit from GPU vs. CPU computations; Gurobi even explain this on their website. So, please clarify and correct/elaborate in the paper! (Also, state the Gurobi version you used.)\n- Please clarify what exactly is being sampled (and to what purpose exactly) in Section 2.3\n- Please justify the IP objective function and clarify/give a reference for how the fractional IP can be turned into a linear IP.", "limitations": "Limitations have by and large been addressed sufficiently.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 4, "strengths": "The novel performance estimation method appears to be well-motivated and leads to the possibility of applying mixed-integer programming to compute an optimal architecture (w.r.t. the utilized performance estimates). The numerical results indicate that this works well in practice, giving somewhat better or comparable results with notable savings in training time. This new NAS pipeline also shows promise for future refinements, e.g., regarding the MIP problems used for the search once performance estimates have been pre-computed, given the inherent flexibility of MIP to model a variety of different aspects.", "weaknesses": "The paper must be thoroughly proofread for English language and grammar/typos. The supplementary document is as long as the main paper, but provides mostly only some small additional information; some things I hoped to find in the supplement were however not included, e.g., an explanation for the MIP objective function and a description or at least literature reference for how to turn the fractional objective into a linear one. Math typesetting especially of optimization programs can be improved. Also, I got the impression that the authors are trying a bit too hard to \"sell\" their ideas; maybe tone down the language a bit (there's very many usages of words like \"impressive\" or \"remarkable\" and similar phrasings praising the paper's results). Finally, there are several parts that remained somewhat unclear to me (see \"Questions\"), so the presentation can also be improved in terms of clarity/rigor.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your thoughtful review of our work.\n\n---\n# Polynomial-time Search Complexity\n\nAs you surmised, the polynomial time referenced here does not pertain to the duration required to solve the ILP problem. Instead, **it denotes the time complexity of the MathNAS algorithm in identifying the optimal architecture, or more precisely, the number of networks that need evaluation within the search space**. Only after evaluating the requisite networks do we proceed to solve the ILP problem. Similar forms of time complexity descriptions have appeared in other MP-NAS works, such as in LayerNAS [1].\n\n[1] Yicheng Fan et al. LayerNAS: Neural Architecture Search in Polynomial Complexity. 2023.\n\n---\n# Network Training\nHere, we clarify the network training aspects within the MathNAS algorithm. \n\nMathNAS operates in two stages: an offline block evaluation stage and an online search stage. In the offline stage, we first assess the accuracy of $m\\* n$ sampled networks and then calculate block performance based on these evaluations. \n\n**[WHEN]** This network evaluation stage (offline stage) indeed encompasses the network training process.\n\n**[WHAT]** Specifically, for our experiments in the MobileNetV3 [2], SuperViT [3] and SuperTransformer [4] search spaces, we utilize networks pretrained from prior work. For the NAS-Bench-201 [5] search space, we rely on the accuracy on the validation set of networks independently trained for 200 epochs. In the revised version, we will elaborate on these offline costs and incorporate them into the overall cost of the MathNAS algorithm.\n\n[2] Andrew Howard et al. Searching for mobilenetv3. 2019.\n\n[3] Chengyue Gong et al. Nasvit: Neural architecture search for efficient vision transformers with gradient conflict aware supernet training. 2021\n\n[4] Hanrui Wang et al. Hat: Hardware-aware transformers for efficient natural language processing. 2020.\n\n[5] Xuanyi Dong et al. Nas-bench-201: Extending the scope of reproducible neural architecture search. 2020.\n\n---\n# Block Architecture Flexibility\nHere, we provide a detailed description of block architecture flexibility.\n\nGiven a search space comprised of $m$ block nodes, each block node has $n$ candidate blocks. These blocks can be of any neural network type, including CNNs and Transformers, with no structural constraints. Additionally, a candidate block can be a 'skip', indicating variability in the number of network blocks.\n\nFor instance, in the case of an inverted residual block, one can choose different numbers of network layers, kernel sizes, and expansion ratios. For a transformer block, one can select varying numbers of encoder/decoder layers, hidden dimensions, and the number of attention module heads.\n\n**As long as the spatial dimensions of the input and output tensors of the candidate blocks match the dimensions at the corresponding positions in the search space, the MathNAS algorithm can effectively conduct the search.**\n\n---\n# Sampling strategy in Section 2.3\nTo compute the accuracy of block $b\\_{i,j}$, we must evaluate the mean change in network accuracy when all networks in the search space containing block $b\\_{i,1}$ undergo a specific block replacement process - switching from $b\\_{i,1}$ to $b\\_{i,j}$ (ref: Equation 3).\n\nThis implies that in order to calculate $b\\_{i,j}^A$, we need to determine the accuracy for $m^{(n-1)}$ networks. However, given the observed inverse relationship between network FLOPs and delta-Accuracy, we can estimate $b\\_{i,j}^A$ based on the accuracy variation of a network with average FLOPs (ref: paper 2.3 Single Network Sampling Strategy).\n\n**In summary, to reduce algorithmic complexity, we sample a specific network from $\\mathcal{N}^{\\Omega}\\_{(i,j)}$ ( i.e., all  $m^{(n-1)}$  networks containing $b\\_{i,j}$ ) whose FLOPs equal the average FLOPs of $\\mathcal{N}^{\\Omega}\\_{(i,j)}$.**\n\nWe use the change in accuracy of this sampled network as a proxy for the average accuracy change of all networks, thereby deriving the accuracy for block $b\\_{i,j}$. Experimental results show this sampling approach introduces minimal error.\n\n---\n# Other Questions\n## Writing Problem:\nThanks for your patient and meticulous review. \nWe have rechecked and corrected the grammar and spelling throughout the paper. \nAdditionally, we've reorganized the Appendix and provided corresponding references in the paper. \nWe have also considered improvements in the formatting of mathematical formulas and refined our choice of words. \nThese writing issues will be addressed in the revised version.\n\n## Use of Gurobi:\nUpon re-examining our code related to the dynamic network experiments, we discovered that when running MathNAS on the TX2 GPU, the equations were actually being solved on the CPU using the Gurobipy. \nSubsequently, the solved architecture was loaded onto the GPU for execution. Hence, the reported search time primarily reflects the equation-solving time on the TX2 CPU, which explains why the reported CPU and GPU solution times are identical. We apologize for any confusion our initial description may have caused and will clarify this matter in the revised version.\n\n## ILP objective function:\nIn our *common response*, we've provided the technical details of how to convert to an ILP problem and solve it. We will add these technical details in our revised version."}, {"review_id": "dDVGCeMmQ1", "reviewer": "Reviewer_qRGY", "summary": "The paper introduces MathNAS, a novel approach to Neural Architecture Search (NAS) that utilizes mathematical programming techniques. MathNAS aims to improve the efficiency and accuracy of architecture search by dividing the search space into smaller building blocks and predicting network performance based on the performance of these blocks. The authors validate the effectiveness of MathNAS on computer vision (CV) and natural language processing (NLP) tasks, showcasing its superior performance compared to state-of-the-art models.", "questions": "1. Can you clarify the approach or strategy employed to divide the networks into individual modules or blocks?\n\n2. Based on observations from Figure 1b, the Floating Point Operations Per Second (FLOPs) appear to have minimal impact on latency. Could you provide an explanation or insight into why this phenomenon occurs?\n\n3. Have you considered implementing a Graph Neural Network (GNN) model designed to predict performance variances that may arise as a result of interchanging different modules within the network? What outcomes or implications might this approach yield?", "limitations": "N/A", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. Efficient Performance Evaluation: MathNAS proposes a general framework for evaluating candidate networks by estimating block performance first and then combining them to predict network performance. This approach greatly improves evaluation efficiency .\n2. Reduced Search Complexity: By establishing a mapping between block performance and network performance, MathNAS transforms NAS into an Integer Linear Programming (ILP) problem, reducing the search complexity to polynomial time .\n3. Superior Results: The authors demonstrate MathNAS's capabilities by considering key performance indices such as accuracy, latency, and energy. The results show that MathNAS outperforms state-of-the-art models in terms of these metrics .", "weaknesses": "1. Lack of Detailed Implementation: The paper provides a high-level overview of MathNAS but lacks detailed implementation information. More specific details about the mathematical programming techniques used and the specific algorithms employed would have been beneficial.\n\n2. Section 2.2 of the paper presents some significant ambiguities that complicate understanding of the proposed method:\n\na. The paper does not clearly explain the definitions of \"inherent capability\" and \"interactive capability\". This makes it challenging to understand their intended meanings and how they function within the given neural network context.\n\nb. There is a lack of clarity on how the changes in these capabilities, represented as $\\Delta \\phi\\left(\\mathcal{B}{(i, 1) \\rightarrow(i, j)}\\right)$ and $\\Delta \\Phi\\left(\\mathcal{B}{(i, 1) \\rightarrow(i, j)}\\right)$, are evaluated. The methodology for these calculations needs to be explained more explicitly.\n\nc. Equation 3 lacks clarity due to the aforementioned uncertainties. Without clear definitions and calculation methods for the terms on the right-hand side, it is impossible to meaningfully interpret or apply this equation.\n\nd. Additionally, the processes of module swapping and internal adjustment are not well-defined. More details on how these operations are performed, both in terms of selecting which modules to swap and how the internal adjustments are made post-swap, are needed for a comprehensive understanding and replication of the method. Does every module have the sample input/output shape?\n\n\n3. Limited Discussion on Generalization: Although the paper mentions MathNAS's remarkable generalization capabilities in designing efficient architectures for NLP tasks, there is limited discussion on the factors contributing to this generalization and how it compares to other NAS methods.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your thoughtful review of our work.\n\n---\n# Clarification about Section 2.2\n## Clarifications on Definition and Calculation of Equation 3\n*The answers here correspond to parts a, b, and c of the original question.*\n\nBoth theoretically and empirically, we have shown that the effects of a specific block switch differs across various architectures. Delving into these discrepancies, we define the calculation of block performance as:\n$$b^{A}\\_{i,j}=\\overline{\\Delta Acc\\left(\\mathcal{N}^{\\Omega}\\_{(i,1) \\rightarrow  (i,j)}\\right )}$$.\n**This formula is designated for the computation of the performance of $b\\_{i,j}$**.\n\nFurthermore, we propose that the effect of block performance on network accuracy should be approached from two angles: inherent capability and interactive capability. These two concepts help illuminate the meaning behind our block performance formula (**though it's important to note they serve explanatory purposes and aren't directly employed in the calculation**). Hence, we have:\n$$\\overline{\\Delta Acc\\left(\\mathcal{N}^{\\Omega}\\_{(i,1) \\rightarrow  (i,j)}\\right )} = \\Delta\\phi(\\mathcal{B}\\_{(i,1)\\rightarrow (i,j)}) + \\Delta\\Phi(\\mathcal{B}\\_{(i,1)\\rightarrow (i,j)})$$.\nWherein:\n- The term *inherent capability* refers to the intrinsic ability of the block.\n- The term *interactive capability* denotes the capacity of a block when considering its influence on other blocks within the network.\n\nTo draw an analogy, consider a team where an individual's performance is not just a reflection of their inherent skill but also the influence they exert on their teammates. Similarly, a network can be viewed as a team composed of blocks.\n\n## Details on Module Switching and Internal Adjustments\n*The answers here correspond to part d of the original question.*\n\nFor all replacement blocks within the search space, a performance evaluation is required. Specifically, to evaluate the performance of block $b\\_{ij}$, we consider the switch from $b\\_{i1}$ to $b\\_{ij}$.\n\nAfter a block swap, there's no need for internal adjustments. This is because for all candidate blocks contained within the $i$-th block node, their input and output tensor spatial dimensions match those in the search space.\n\n---\n# Other Questions\n## Detailed implementation:\nIn our *common response*, we've provided detailed technical specifics regarding the solution to the ILP equation. These technical details will be supplemented in our revised version.\n\n## Discussion of generalization on NLP tasks:\nHere, we'd like to elucidate the generalization capability of MathNAS across diverse tasks.\n\nAs mentioned in the paper, MathNAS is applicable to various block architectures, including convolutional blocks and transformer blocks.\n**The architectural applicability of MathNAS is task-agnostic.**\nThis suggests that, for a range of tasks spanning CV and NLP, MathNAS is theoretically applicable as long as the search space can be structured in a block format.\n\nMoreover, the Transformer architecture has demonstrated significant potential in NLP tasks.\nExperiments further revealed that MathNAS exhibits exceptional performance within the search spaces of Transformer architectures, including SuperViT and SuperTransformer. \nThis, to some extent, highlights the commendable task generalization of MathNAS on NLP tasks.\n\n## Division of blocks:\nA detailed description of the block division for different search spaces can be found in the Appendix D.1. \n\nHere, we provide a brief overview of our block partitioning strategy:\n\n- For the **MobileNetV3** search space, we adhere to the original block division, considering one inverted residual structure as a single block.\n- For the **SuperTransformer** search space, we classify two encoder layers as one block and one decoder layer as another block.\n- For the **SuperViT** search space, we again follow the original block categorization, defining either a CNN or a Transformer block as a single block.\n - For the **NAS-Bench-201** search space, our concept of a block corresponds to an edge operation in a GNN, where each operation on an edge equates to a block.\n\n## Interpretation of latency experimental results:\nFigure 1 illustrates the impact of FLOPs on network performance (accuracy, latency, energy) during block switches. In other words, it reveals the contribution of blocks to the performance of networks with varying FLOPs. \n\nThe minimal variations in latency shown in Figure 1b suggest that **the contributions of different blocks to the network's latency are independent**, which aligns with our understanding. Taking a network composed of sequentially connected blocks as an example, the network's required latency is roughly the sum of the independent latencies needed for each block.\n\n## Implementation on the GNN model:\n\nIn fact, we believe that our experimental verification of MathNAS on the NAS-Bench-201 search space can serve as a testament to its compatibility with GNN networks. \n\nNAS-Bench-201 represents a micro search space, consisting of five identical GNN blocks where the edges of a GNN can select different operations. \n\nIn the context of the paper, the block switch operation, when applied to NAS-Bench-201, essentially refers to changing the operation on a particular edge while keeping the operations on other edges constant. This effect mirrors the application of MathNAS to a complete GNN model.\nHence, from the validation of MathNAS on NAS-Bench-201, we can infer its suitability for GNN networks. \n\nWe will clarify this point in our revised version.\n"}]

Author rebuttal:
Thank you all for your thoughtful reviews. Here, we respond to some common concerns across all reviewers.

---
# Paper Citations, Novelty, and Supplementary Experiments
Existing blockwise methods such as DNA [1], DONNA [2], and LANA [3] use block distillation techniques to block the teacher model, obtaining the architecture of blocks to be replaced and their performance evaluation. Following this, they use the performance of each block to guide the algorithm in finding models with superior performance.

Recent work [4] has pointed out the limitations of such methods. They depend on an excellent teacher network due to their use of distillation techniques. Furthermore, previous block performance estimation methods are unable to effectively predict actual block performance. Additionally, these methods are only suitable for the macro search space. MathNAS overcomes the above limitations:
- It does not depend on distillation but proposes a new block evaluation method based on the observed relationship between FLOPs and delta-Accuracy. This method is mathematically efficient and succinct, and it has been theoretically validated across different search spaces.
- It applies to a wider variety of search spaces, beyond the classical ones apart from the macro search space, such as the micro search space of NB201 (ref: rebuttal pdf).
- Its evaluation of block performance and network accuracy prediction is more precise (ref: rebuttal pdf).
- It can find more superior architectures based on a full-space search, holding true even when compared to non-blockwise NAS methods. Moreover, the time complexity of the search algorithm is at a polynomial level.

*We have conducted supplementary experiments to compare the applicability of MathNAS and previous blockwise methods across different search spaces, as well as the efficacy of network accuracy predictions. Please refer to the attached pdf for details.*

In the revised version, we will include these references, discuss the differences, and provide supplementary experimental validation.

[1] Changlin Li et al. Blockwisely supervised neural architecture search with knowledge distillation. 2020.

[2] Bert Moons et al. Distilling optimal neural networks: Rapid search in diverse spaces. 2021.

[3] Pavlo Molchanov et al. LANA: latency aware network acceleration. 2022.

[4] Thomas Chau et al. BLOX: Macro Neural Architecture Search Benchmark and Algorithms. 2022.

---
# Search Cost
The search cost of MathNAS consists of two stages: offline network pre-training (conducted only once) and online real-time search. 
- During the offline network pre-training, MathNAS evaluates block performance once.
- During online searching, MathNAS is capable of multiple real-time searches based on the current hardware resource constraints. 

To negate the influence of variations in GPU models and versions on the pre-training time, and to facilitate comparisons by future researchers, we have adopted pre-trained networks provided by existing works (MobileNet [2], SuperViT [3], SuperTransformer [4], NAS-Bench-201[5]). Consequently, all mentions of MathNAS's search cost in the paper refer solely to the real-time search time on edge devices (i.e., the time taken to solve the ILP problem).

In the revised version, we will consider adding the offline network pre-training time and will adjust the existing statements accordingly for greater clarity.

[5] Andrew Howard et al. Searching for mobilenetv3. 2019.

[6] Chengyue Gong et al. Nasvit: Neural architecture search for efficient vision transformers with gradient conflict aware supernet training. 2021

[7] Hanrui Wang et al. Hat: Hardware-aware transformers for efficient natural language processing. 2020.

[8] Xuanyi Dong et al. Nas-bench-201: Extending the scope of reproducible neural architecture search. 2020.

---
# Searching Equation Solving Details
In this section, we describe in detail the solution of the fractional objective function programming equation proposed in the paper. 
The solution is divided into two steps. 
1. Convert the original equation into an integer linear programming equation.
2. Solve the ILP equation.

### Equation Transformation
In order to transform the equation into an ILP problem, we first perform variable substitution on the original equation [9].
$$
\text{let}\quad b^{\widetilde{B}}\_{i,j}=\cfrac{b^B\_{i,j}}{\sum\_{i=1}^m\sum\_{i=1}^nb^F\_{i,j}*b^B\_{i,j}},\quad z=\cfrac{1}{\sum\_{i=1}^m\sum\_{i=1}^nb^F\_{i,j}*b^B\_{i,j}}
$$
Then the original equation can be transformed into the following integer linear programming problem:

$$
\begin{split}
     &O = \min\limits\_{b^{\widetilde{B}},z}{ (\sum\_{i=1}^m\sum\_{j=1}^nb^A\_{i,j}\*b^{\widetilde{B}}\_{i,j}\*\overline{\mathcal{F}(\mathcal{N})})} \\\\
     &s.t. \\\\
     &(Lat(\widetilde{\mathcal{N}})-\hat{L})*z \leq \sum\_{i=1}^m\sum\_{j=1}^nb^L\_{i,j}*b^{\widetilde{B}}\_{i,j},  (Eng(\widetilde{\mathcal{N}})-\hat{E})*z \leq \sum\_{i=1}^m\sum\_{j=1}^nb^E\_{i,j}*b^{\widetilde{B}}\_{i,j}  \\\\
    &\forall{1\leq i \leq m}, \sum\_{j=1}^nb^{\widetilde{B}}\_{i,j}=z, b^{\widetilde{B}}\_{i,j}\in\left\\{0,z\right\\}.
\end{split} 
$$

### ILP Solving
To solve the ILP equations, we use the off-the-shelf Linprog Python package and the Gurobipy Python package to find feasible candidate solutions.
- Linprog is a basic integer programming solver that can be used on almost all edge devices, even on the resource-constrained Raspberry Pi. We use it to implement the branch and bound method and solve the ILP problem.
- Gurobipy is a more powerful solver, which has built-in a variety of advanced solving algorithms such as heuristic algorithms, and can flexibly utilize all available hardware resources on the device. Although Gurobipy is powerful, it requires more hardware resources than Linprog.

Therefore, for devices with limited hardware resources, we use Linprog for searching. For well-resourced devices, we use Gurobipy.

[9] Siegfried Schaible et al. Fractional programming. 1983.

Meta-review: This study proposes a mathematical programming based NAS method named MathNAS, which is composed of three steps, block performance estimation, network performance prediction, and solving an integer linear programming problem to perform NAS based on the established mapping between block performance and network performance. After rebuttal, most reviewers acknowledged that the authors have addressed the concerns, and all reviewers suggested acceptance for this paper. The AC inspected the paper and all the discussions, and agreed that the paper should be accepted for the clarity of presentation, the novelty of the method, and the strong experimental performance.
Decision: Accept (poster)