videos. Non-local blocks are a particular case in our proposed search space, and our attention cells are discovered automatically in a data-driven way instead of being manually designed.

**NAS - Search Space.** Search space is crucial for NAS. Randwire [@xie2019exploring] shows that one random architecture from a carefully designed search space can achieve competitive performance on image recognition. NASNet [@zoph2018learning] proposes to search for convolutional cells that can be stacked multiple times to form the entire architecture. Auto-DeepLab [@liu2019auto] proposes a two-level hierarchical architecture search space for semantic image segmentation. AssembleNet [@Ryoo2020AssembleNet:] proposes to search for the connectivity between multi-stream convolutional blocks for video classification. They all focus on finding convolutional cells or networks for the end task. Different from them, our proposed search space uses attention as the primary building component instead of convolution.

**NAS - Search Algorithm.** Various search algorithms have been explored in NAS, such as random search [@li2019random; @Yu2020Evaluating], reinforcement learning [@baker2016designing; @zoph2016neural; @zoph2018learning; @zhong2018practical], evolutionary algorithms [@xie2017genetic; @real2017large; @real2019regularized], Bayesian optimization (BO) [@kandasamy2018neural; @cao2018learnable], and differentiable methods [@liu2018darts]. We have tried using GPB (belonging to the category of BO) to search for desired attention cells. We also develop a differentiable formulation of our proposed search 