REVIEW 4 major objections 5 minor 37 references
MANAS: Multi-Agent Neural Architecture Search
T0 review · 4 major / 5 minor · reviewed 2026-08-14 · deepseek-v4-flash
Pith's one-line read The paper claims that treating each edge of a DARTS cell as an online-learning agent, with shared weights and bandit-style updates, finds better architectures than DARTS at about one-eighth of its memory.
desk verdict A useful multi-agent framing and honest empirical effort, but the central regret guarantee does not cover the actual algorithm and the missing RandomNAS-WS baseline undercuts the empirical claims. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
The central object is a per-edge bandit attached to the DARTS cell: agent $A^i$ controls edge $(i,j)$ and chooses one of $K$ operations, and the joint action profile is the architecture $Z_t$. The key identity carrying the argument is the factored regret: under a linear decomposition of the validation loss, the joint worst-case regret splits into a sum of per-agent regrets, letting each agent run an independent bandit in parallel, EXP3 for MANAS and least-squares plus Zipf for MANAS-LS. Weight sharing supplies the common network weights, so no operation parameters are duplicated, which is what gives the memory reduction.
What would settle it
Run MANAS against a uniform-random weight-sharing controller that samples the same architectures and updates the shared weights identically but never updates the sampling distribution, using the same search budget on CIFAR-10 and on the three new datasets; if the random controller matches MANAS's accuracy, the claim that the bandit coordination is what produces the gains is falsified.
Extended reading notes
Core claim
MANAS is a multi-agent algorithm for neural architecture search in which each directed edge of the DARTS cell is an agent with $K$ possible operations. At every round the agents sample a sparse architecture, the shared weights are updated by backpropagation on the training loss, and the validation loss is used by each agent to update its own estimate of operation quality. Two credit-assignment schemes are proposed: MANAS uses an EXP3-style importance-weighted update with softmax sampling, while MANAS-LS approximates the validation loss as a linear combination of operation contributions and samples with a Zipf distribution. The authors claim that these mechanisms coordinate implicitly through the joint loss, reduce memory from $O(NK)$ to $O(N)$, allow direct search on 20-cell CIFAR-10 and 14-cell ImageNet networks, and deliver test errors of 2.63% and 2.52% on CIFAR-10 and 26.15% on ImageNet, beating DARTS under the same evaluation protocol while using roughly one eighth of its GPU memory.
Load-bearing premise
The regret bound assumes every other agent's actions are fixed for all $T$ rounds, while in the actual algorithm every agent updates every round; if the coupled, non-stationary system is not covered by that assumption, the theoretical guarantee does not apply to MANAS as run.
Editorial extensions
If this is right
- Search can be run directly on the final network depth, so architecture cells do not need to be repeated; the paper reports gains from this on CIFAR-10.
- Memory use drops to about one eighth of DARTS, making direct search on ImageNet feasible; the paper reports a 0.85 percentage-point improvement over DARTS and SNAS when searching on ImageNet directly.
- The regret bounds state that, under the paper's assumptions, cumulative regret grows only as $O(\sqrt{T})$ for MANAS and simple regret decays exponentially for MANAS-LS, so exploration and exploitation are balanced without a hand-tuned reinforcement-learning reward.
- On three new datasets, Sport-8, Caltech-101 and MIT-67, MANAS outperforms DARTS and random sampling, especially at 14 cells, suggesting the method transfers beyond CIFAR-10.
Reading between the lines
- If the fixed-environment assumption in the regret proof were replaced by a non-stationary or game-theoretic analysis, the same algorithm might enjoy a joint no-regret guarantee; absent that, the theoretical guarantee should be read as per-agent against frozen opponents.
- The paper's own experiments leave open that a uniform-random weight-sharing controller with the same memory savings could match MANAS's accuracy; a direct head-to-head on the same search budget would isolate the contribution of the bandit updates.
- Treating the number of cells as a searchable quantity, rather than fixing it, is a natural next step, since the paper finds that the best cell for an 8-cell network is not the best cell for a 14-cell network.
- Because MANAS needs no differentiable architecture objective, it could in principle be combined with non-differentiable hardware metrics such as latency or energy during search, something gradient-based NAS cannot do directly.
Signed reviews
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper frames neural architecture search as a multi-agent online learning problem. Each edge of the DARTS-style cell is controlled by an agent that samples an operation from a private policy, receives the shared validation loss as feedback, and updates its policy. Two instantiations are proposed: MANAS, which uses an EXP3-style softmax update (Eq. 6), and MANAS-LS, which fits a linear model to the validation loss and samples according to a Zipf distribution. The paper claims cumulative regret O(sqrt(T)) for MANAS, exponential simple regret O(e^{-T/H}) for MANAS-LS, a memory reduction to roughly 1/8 of DARTS, state-of-the-art results on CIFAR-10 and ImageNet, and favorable comparisons against random baselines on Sport-8, Caltech-101, and MIT-67. A Gaussian Squeeze Domain experiment is included to illustrate the regret behavior.
Significance. If correct, the manuscript would introduce a genuinely new perspective to NAS: replacing the continuous relaxation of DARTS with a distributed bandit formulation that can search directly over final network depths while retaining theoretical guarantees. The paper deserves credit for several concrete strengths: the agent formulation is clear, the memory-efficient search over 20-cell networks is valuable, the three additional datasets with 8-run means and standard deviations are a step toward reducing benchmark overfitting, and the Gaussian Squeeze Domain experiment makes an explicit empirical connection to the theoretical bound. However, the central advertised guarantees do not hold as stated for the actual algorithm. Theorem 2 is a per-agent bound under a frozen background of other agents, not a bound on the joint regret defined in Eq. (3), and Theorem 1's exponential-rate claim has a scaling problem because H is built from cumulative losses. The empirical evaluation also omits the weight-sharing random-search baseline that would isolate the contribution of the learned updates.
major comments (4)
- [§5.3, Appendix D.2, Eq. (3)] Theorem 2 bounds sum_i R*^i_T(pi^{A_i}), where each per-agent regret is defined with a^{-i} fixed for all T rounds. This is not the joint regret in Eq. (3): in Algorithm 1 every agent updates its policy every round, so the loss sequence seen by any one agent is nonstationary because the other agents are also learning. Moreover, summing per-agent regrets with different frozen background action profiles does not compare against min_a sum_t L_t(a), the joint benchmark in Eq. (3). Consequently the abstract's claim of 'vanishing regrets' for the actual coupled dynamics is unsupported. The authors should either prove a bound for the joint dynamics or explicitly restate the contribution as a per-agent guarantee under a stationary background.
- [Theorem 1, Appendix D.1] The stated simple-regret bound O(e^{-T/H}) is not justified by the proof. H is defined through the cumulative quantities B_T^{(A_i)}[j] = sum_{t=1}^T beta_t^{(A_i)}[j], so H grows linearly with T for any non-zero mean gap. Then T/H tends to a constant, not to infinity, and O(e^{-T/H}) is not an exponentially decaying guarantee. The proof's exponent, obtained by substituting Delta_k = B_T[k] - B_T[k*_i] into exp(-(Delta_1)^2 T / (2 N log K / lambda_min)), scales as T^3 for stationary gaps, which is not expressed by the claimed T/H form. In addition, the proof assumes a uniform exploration probability 1/log K, while Section 5.1 specifies Zipf sampling; the analysis therefore does not cover the proposed sampler.
- [§6.3, Figure 2] The random baseline in Section 6.3 samples eight architectures uniformly and trains each from scratch. This is a random-sampling control, not the weight-sharing random search of Li and Talwalkar (RandomNAS-WS), which is the appropriate baseline for isolating the effect of the bandit updates: RandomNAS-WS has the same memory advantage over DARTS and uses the same weight-sharing protocol, differing only in that it does not update sampling distributions. Without this comparison, the empirical claim that MANAS's learned credit assignment drives the observed gains is not established, and the memory-efficiency claim alone does not differentiate MANAS from the omitted baseline.
- [Eq. (5), Eq. (9), Appendix D.1] There is a mismatch between the MANAS-LS algorithm as implemented and the estimator analyzed in the proof. Section 5.1 defines the credit assignment as a least-squares fit over the collected architectures (Eq. 5), while Appendix D.1 analyzes the ComBand-style inverse-propensity estimator ~beta_t = L_t^{(val)} P^dagger Z_t (Eq. 9) under a uniform sampling distribution. These are different estimators, and the paper does not show that the batch least-squares update inherits the regret properties proved for Eq. (9). The theoretical guarantee for MANAS-LS is therefore for a different algorithm than the one evaluated in Section 6.
minor comments (5)
- [Algorithm 1, line 1] The initialization says each policy is uniform over j in {1,...,N}, but each agent selects among K operations; this appears to be a typo and should read {1,...,K}.
- [Table 1] The reported search costs are internally surprising: 20 cells with 500 epochs cost 2.8 GPU days, while 8 cells with 50 epochs cost 0.8 GPU days. The second has only 1/25 of the search budget, so the costs do not scale as the text would suggest; please clarify whether the numbers are per-run, per-architecture, or otherwise normalized.
- [Figure 2] The subplots use different y-axis scales, and on Sport-8 the 14-cell MANAS result is visibly worse than the 8-cell result, while the text states that the 14-cell setting is better. The figure and the discussion should be reconciled, and the authors should offer an explanation for the non-monotonic behavior.
- [Section 6.3] The text switches between 'random sampling' and 'random search' without defining the distinction; since the appendix explicitly samples a fixed number of architectures, the terminology should be made consistent.
- [Introduction] The sentence 'as show in Section 6 of this work' should read 'as shown in Section 6', and there are several typographical errors elsewhere (e.g., '3 news datasets' and the inconsistent author name 'Xang Xu' vs. 'Hang Xu').
Circularity Check
No load-bearing circularity: results are external-benchmark-based and the theory is a derivation; the only notable self-citation is non-load-bearing, and the main proof gaps are correctness risks, not circularity.
full rationale
The empirical claims (CIFAR-10, ImageNet, Sport-8, Caltech-101, MIT-67) are evaluated against external benchmarks and are not produced by fitting constants or by renaming inputs, so they cannot reduce to the search algorithm's own definitions. The regret analyses are derivations from standard EXP3/ComBand-style arguments (Auer et al. 2002; Cesa-Bianchi and Lugosi 2012) and are not fitted to the observed NAS losses. The Gaussian Squeeze Domain experiment compares the empirical cumulative regret with the derived O(N sqrt(T K log K)) bound rather than defining the result from the bound. The self-citation to Yang et al. (2020), an overlapping-author paper, is used only to corroborate that searching on 8 cells and stacking is a coarse approximation, a point the present paper also demonstrates directly in Section 6; it is not load-bearing. Two genuine weaknesses are visible in the appended material, but they are not circular. First, Theorem 2 in Appendix D.2 is proved only for a per-agent regret with a^{-i} fixed for all T rounds, while Algorithm 1 updates every agent every round, so the claimed joint cumulative regret of Eq. (3) is not established. Second, in Theorem 1, H is defined from cumulative B_T, so O(e^{-T/H}) is not a genuine exponential decay in T as written. These are unsupported-claim and correctness issues, not cases of a prediction being equivalent to its input by construction.
Assumptions & free parameters
free parameters (2)
- Softmax temperature eta for MANAS =
Tuned on validation; exact value not reported
- Tuning parameter gamma =
Tuned on validation; not defined in the main text
assumptions (4)
- domain assumption Shared weights w_t are a valid proxy for w*(Z_t) in the validation loss L_t(Z_t, w_t).
- ad hoc to paper For MANAS-LS, the validation loss satisfies L_s = beta_s^T Z_s for a time-varying beta_s (Eq. 4).
- domain assumption beta_t lies in the linear span of sparse architecture vectors, and losses are bounded in [0,1] (Appendix D.1).
- domain assumption For Theorem 2, the other agents' actions a^{-i} are fixed for T rounds (Appendix D.2).
Cite this review
Pith. "Pith review of MANAS: Multi-Agent Neural Architecture Search." pith.science (2026). https://pith.science/paper/YEG3IOGS
@misc{pith2026190901051,
author = {Pith},
title = {Pith review of: MANAS: Multi-Agent Neural Architecture Search},
year = {2026},
howpublished = {\url{https://pith.science/paper/YEG3IOGS}},
note = {Machine review of arXiv:1909.01051}
}
read the original abstract
The Neural Architecture Search (NAS) problem is typically formulated as a graph search problem where the goal is to learn the optimal operations over edges in order to maximise a graph-level global objective. Due to the large architecture parameter space, efficiency is a key bottleneck preventing NAS from its practical use. In this paper, we address the issue by framing NAS as a multi-agent problem where agents control a subset of the network and coordinate to reach optimal architectures. We provide two distinct lightweight implementations, with reduced memory requirements (1/8th of state-of-the-art), and performances above those of much more computationally expensive methods. Theoretically, we demonstrate vanishing regrets of the form O(sqrt(T)), with T being the total number of rounds. Finally, aware that random search is an, often ignored, effective baseline we perform additional experiments on 3 alternative datasets and 2 network configurations, and achieve favourable results in comparison.
Figures
Reference graph
Works this paper leans on
-
[1]
Best of both worlds: Stochastic & adversarial best-arm identification
Yasin Abbasi-Yadkori, Peter Bartlett, Victor Gabillon, Alan Malek, and Michal Valko. Best of both worlds: Stochastic & adversarial best-arm identification. In Conference on Learning Theory (COLT), 2018
work page 2018
-
[2]
The nonstochastic multiarmed bandit problem
Peter Auer, Nicolo Cesa--Bianchi , Yoav Freund, and Robert E Schapire. The nonstochastic multiarmed bandit problem. SIAM journal on computing, 32 0 (1): 0 48--77, 2002
work page 2002
-
[3]
Regret analysis of stochastic and nonstochastic multi-armed bandit problems
S \'e bastien Bubeck, Nicolo Cesa-Bianchi, et al. Regret analysis of stochastic and nonstochastic multi-armed bandit problems. Foundations and Trends in Machine Learning , 5 0 (1): 0 1--122, 2012
2012
-
[4]
Proxyless NAS : Direct neural architecture search on target task and hardware
Han Cai, Ligeng Zhu, and Song Han. Proxyless NAS : Direct neural architecture search on target task and hardware. In International Conference on Learning Representations (ICLR), 2019
work page 2019
-
[5]
Combinatorial bandits
Nicolo Cesa-Bianchi and G \'a bor Lugosi. Combinatorial bandits. Journal of Computer and System Sciences, 78 0 (5): 0 1404--1422, 2012
2012
-
[6]
Counterfactual exploration for improving multiagent learning
Mitchell K Colby, Sepideh Kharaghani, Chris HolmesParker, and Kagan Tumer. Counterfactual exploration for improving multiagent learning. In Autonomous Agents and Multiagent Systems (AAMAS 2015), pages 171--179. International Foundation for Autonomous Agents and Multiagent Systems, 2015
work page 2015
-
[7]
Very deep convolutional networks for text classification
Alexis Conneau, Holger Schwenk, Lo \" c Barrault, and Yann Lecun. Very deep convolutional networks for text classification. In European Chapter of the Association for Computational Linguistics: Volume 1, Long Papers, pages 1107--1116, 2017
work page 2017
-
[8]
Autoaugment: Learning augmentation policies from data
Ekin D Cubuk, Barret Zoph, Dandelion Mane, Vijay Vasudevan, and Quoc V Le. Autoaugment: Learning augmentation policies from data. arXiv:1805.09501, 2018
arXiv 2018
Show all 37 references
-
[9]
ImageNet : A large-scale hierarchical image database
Jia Deng, Wei Dong, Richard Socher, Li-Jia Li, Kai Li, and Li Fei-Fei. ImageNet : A large-scale hierarchical image database. In Computer Vision and Pattern Recognition (CVPR), pages 248--255, 2009
2009
-
[10]
Learning generative visual models from few training examples: An incremental bayesian approach tested on 101 object categories
Li Fei-Fei, Rob Fergus, and Pietro Perona. Learning generative visual models from few training examples: An incremental bayesian approach tested on 101 object categories. Computer Vision and Image Understanding, 106 0 (1): 0 59--70, 2007
2007
-
[11]
Freedman
David A. Freedman. On tail probabilities for martingales. The Annals of Probability, pages 100--118, 1975
1975
-
[12]
Deep pyramidal residual networks
Dongyoon Han, Jiwhan Kim, and Junmo Kim. Deep pyramidal residual networks. In Computer Vision and Pattern Recognition (CVPR), pages 5927--5935, 2017
2017
-
[13]
Deep residual learning for image recognition
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In Computer Vision and Pattern Recognition (CVPR), pages 770--778, 2016
2016
-
[14]
Densely connected convolutional networks
Gao Huang, Zhuang Liu, Laurens Van Der Maaten, and Kilian Q Weinberger. Densely connected convolutional networks. In Computer Vision and Pattern Recognition (CVPR), pages 4700--4708, 2017
2017
-
[15]
Imagenet classification leaderboard
ByungSoo Ko. Imagenet classification leaderboard. https://kobiso.github.io/Computer-Vision-Leaderboard/imagenet, 2019
2019
-
[16]
Learning multiple layers of features from tiny images
Alex Krizhevsky. Learning multiple layers of features from tiny images. Technical report, University of Toronto, 2009
2009
-
[17]
What, where and who? classifying events by scene and object recognition
Li-Jia Li and Li Fei-Fei. What, where and who? classifying events by scene and object recognition. In International Conference on Computer Vision (ICCV), pages 1--8, 2007
2007
-
[18]
Random search and reproducibility for neural architecture search
Liam Li and Ameet Talwalkar. Random search and reproducibility for neural architecture search. arXiv:1902.07638, 2019
1902 arXiv
-
[19]
Progressive neural architecture search
Chenxi Liu, Barret Zoph, Maxim Neumann, Jonathon Shlens, Wei Hua, Li-Jia Li, Li Fei-Fei, Alan Yuille, Jonathan Huang, and Kevin Murphy. Progressive neural architecture search. In European Conference on Computer Vision (ECCV), pages 19--34, 2018 a
2018
-
[20]
Hierarchical representations for efficient architecture search
Hanxiao Liu, Karen Simonyan, Oriol Vinyals, Chrisantha Fernando, and Koray Kavukcuoglu. Hierarchical representations for efficient architecture search. In International Conference on Learning Representations (ICLR), 2018 b
2018
-
[21]
DARTS : Differentiable architecture search
Hanxiao Liu, Karen Simonyan, and Yiming Yang. DARTS : Differentiable architecture search. In International Conference on Learning Representations (ICLR), 2019
2019
-
[22]
Regularizing and optimizing LSTM language models
Stephen Merity, Nitish Shirish Keskar, and Richard Socher. Regularizing and optimizing LSTM language models. In International Conference on Learning Representations (ICLR), 2018
2018
-
[23]
Efficient neural architecture search via parameter sharing
Hieu Pham, Melody Guan, Barret Zoph, Quoc Le, and Jeff Dean. Efficient neural architecture search via parameter sharing. In International Conference on Machine Learning (ICML), pages 4092--4101, 2018
2018
-
[24]
Recognizing indoor scenes
Ariadna Quattoni and Antonio Torralba. Recognizing indoor scenes. In Computer Vision and Pattern Recognition (CVPR), pages 413--420, 2009
2009
-
[25]
QMIX : Monotonic value function factorisation for deep multi-agent reinforcement learning
Tabish Rashid, Mikayel Samvelyan, Christian Schroeder Witt, Gregory Farquhar, Jakob Foerster, and Shimon Whiteson. QMIX : Monotonic value function factorisation for deep multi-agent reinforcement learning. In International Conference on Machine Learning (ICML), pages 4292--4301, 2018
2018
-
[26]
Large-scale evolution of image classifiers
Esteban Real, Sherry Moore, Andrew Selle, Saurabh Saxena, Yutaka Leon Suematsu, Jie Tan, Quoc V Le, and Alexey Kurakin. Large-scale evolution of image classifiers. In International Conference on Machine Learning (ICML), pages 2902--2911, 2017
2017
-
[27]
Regularized evolution for image classifier architecture search
Esteban Real, Alok Aggarwal, Yanping Huang, and Quoc V Le. Regularized evolution for image classifier architecture search. arXiv:1802.01548, 2018
2018 arXiv
-
[28]
Evaluating the search phase of neural architecture search
Christian Sciuto, Kaicheng Yu, Martin Jaggi, Claudiu Musat, and Mathieu Salzmann. Evaluating the search phase of neural architecture search. arXiv:1902.08142, 2019
1902 arXiv
-
[29]
Inception-v4, Inception-ResNet and the impact of residual connections on learning
Christian Szegedy, Sergey Ioffe, Vincent Vanhoucke, and Alexander A Alemi. Inception-v4, Inception-ResNet and the impact of residual connections on learning. In AAAI Conference on Artificial Intelligence, 2017
2017
-
[30]
SNAS : Stochastic neural architecture search
Sirui Xie, Hehui Zheng, Chunxiao Liu, and Liang Lin. SNAS : Stochastic neural architecture search. In International Conference on Learning Representations (ICLR), 2019
2019
-
[31]
NAS evaluation is frustratingly hard
Antoine Yang, Pedro M Esperan c a, and Fabio M Carlucci. NAS evaluation is frustratingly hard. In International Conference on Learning Representations (ICLR), 2020
2020
-
[32]
ShuffleNet : An extremely efficient convolutional neural network for mobile devices
Xiangyu Zhang, Xinyu Zhou, Mengxiao Lin, and Jian Sun. ShuffleNet : An extremely efficient convolutional neural network for mobile devices. In Conference on Computer Vision and Pattern Recognition (CVPR), pages 6848--6856, 2018
2018
-
[33]
Neural architecture search with reinforcement learning
Barret Zoph and Quoc Le. Neural architecture search with reinforcement learning. In International Conference on Learning Representations (ICLR), 2017
2017
-
[34]
Learning transferable architectures for scalable image recognition
Barret Zoph, Vijay Vasudevan, Jonathon Shlens, and Quoc V Le. Learning transferable architectures for scalable image recognition. In Computer Vision and Pattern Recognition (CVPR), pages 8697--8710, 2018
2018
-
[35]
@esa (Ref
\@ifxundefined[1] #1\@undefined \@firstoftwo \@secondoftwo \@ifnum[1] #1 \@firstoftwo \@secondoftwo \@ifx[1] #1 \@firstoftwo \@secondoftwo [2] @ #1 \@temptokena #2 #1 @ \@temptokena \@ifclassloaded agu2001 natbib The agu2001 class already includes natbib coding, so you should ...
-
[36]
\@lbibitem[] @bibitem@first@sw\@secondoftwo \@lbibitem[#1]#2 \@extra@b@citeb \@ifundefined br@#2\@extra@b@citeb \@namedef br@#2 \@nameuse br@#2\@extra@b@citeb \@ifundefined b@#2\@extra@b@citeb @num @parse #2 @tmp #1 NAT@b@open@#2 NAT@b@shut@#2 \@ifnum @merge>\@ne @bibitem@firs...
-
[37]
linearity of convolution
@open @close @open @close and [1] URL: #1 \@ifundefined chapter * \@mkboth \@ifxundefined @sectionbib * \@mkboth * \@mkboth\@gobbletwo \@ifclassloaded amsart * \@ifclassloaded amsbook * \@ifxundefined @heading @heading NAT@ctr thebibliography [1] @ \@biblabel @NAT@ctr \@bibset...
2008
Reviewed August 14, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.