summaries: This work focuses on anytime pixel-level recognition (e.g., semantic segmentation). They propose to add intermediate exists in the architecture for anytime inference. They also consider spatial confidence adaptivity in their network, where they only execute subsequent layers on a small set of non-confidence pixels and obtain the features of other positions via interpolation. They apply the method to semantic segmentation and human pose estimation and demonstrate a reduction in FLOPs and good anytime performance for both tasks.

summaries: This paper proposes an anytime method for pixel recognition tasks like semantic segmentation and human pose estimation. The key idea is to design a network with multiple "early exits", from which the network could make predictions using a corresponding prediction head. Thus, depending on criteria like budget or confidence, the network could decide where to exit and therefore leads to different accuracy-computation operating points (i.e. its anytime property).   The technical contributions are mainly on two parts. The first contribution is a re-design of prediction heads (denoted as RH in the paper) at each early exits, mainly to tackle the difference of granularity for different intermediate feature maps. Another contribution is a confidence-based adaptive filtering mechanism that decides how to allocate computation budgets across spatial regions. Specifically, at each exit, the max prediction scores are used as a measure such that all spatial pixels that exceeds certain score threshold will not be processed in later stages.   The authors evaluated their methods on two tasks (Cityscapes for semantics segmentation and MPII for human pose estimation) and demonstrated that their full-blown method yields a better accuracy-computation tradeoff, compared to variants of the proposed approach and several previous methods.    ------------------------- POST REBUTTAL -------------------------  The authors have addressed most of my concerns in their response. Also, after some discussions on the issue of lacking positive signals from wallclock time metric, I buy the arguments to position this work as a forward looking exploration in the alternative space to methods that are chosen in current hardware lottery. With this, I will raise my rating to positive inclined.

summaries: The paper proposes a new task called "anytime" prediction, which requires a model to make a progression of predictions, which might be halted at any time. The authors then also introduce an end-to-end model for this problem. The main two components behind the proposed model are: (1) a cascade of “exits” enabling the model to make progressive predictions while taking into account accuracy vs computational cost tradeoff; (2) Confidence Adaptivity, which allows the model to focus on the less confident pixel prediction. The authors implement their approach using HRNet baseline and demonstrate improved performance and efficiency on semantic segmentation and pose prediction tasks.

summaries: The paper presents adaptive and anytime methods for semantic segmentation and pose recognition. Both of these are "pixel-level" tasks where the model is expected to output a prediction for each pixel in the input image. Their adaptive method, that performs variable amounts of computation depending on the input and the budget, with the amount of computation devoted to a given pixel varying from one part of the image to another. This is done by adding early exits to the base model architecture, and modifying the convolution layers to perform sparse computation on a subset of locations followed by interpolation. Experiments are done on Cityscapes semantic segmentation and MPII pose estimation benchmarks.

abstractText: Anytime inference requires a model to make a progression of predictions which might be halted at any time. Prior research on anytime visual recognition has mostly focused on image classification. We propose the first unified and end-toend model approach for anytime pixel-level recognition. A cascade of “exits” is attached to the model to make multiple predictions and direct further computation. We redesign the exits to account for the depth and spatial resolution of the features for each exit. To reduce total computation, and make full use of prior predictions, we develop a novel spatially adaptive approach to avoid further computation on regions where early predictions are already sufficiently confident. Our full model with redesigned exit architecture and spatial adaptivity enables anytime inference, achieves the same level of final accuracy, and even significantly reduces total computation. We evaluate our approach on semantic segmentation and human pose estimation. On Cityscapes semantic segmentation and MPII human pose estimation, our approach enables anytime inference while also reducing the total FLOPs of its base models by 44.4% and 59.1% without sacrificing accuracy. We compare our method with deep equilibrium networks, as well as a feature-based stochastic sampling approach, and we show that the accuracy-computation curve of our method dominates them.

authors:
Manuel Amthor
Erik Rodner
Joachim Denzler

title: Impatient dnns-deep neural networks with dynamic time budgets

venue: arXiv preprint arXiv:1610.02850,

authors:
Mykhaylo Andriluka
Leonid Pishchulin
Peter Gehler
Bernt Schiele

title: 2d human pose estimation: New benchmark and state of the art analysis

venue: In CVPR,

authors:
Shaojie Bai
Vladlen Koltun
J Zico Kolter

title: Multiscale deep equilibrium models

venue: arXiv preprint arXiv:2006.08656,

authors:
Shijie Cao
Lingxiao Ma
Wencong Xiao
Chen Zhang
Yunxin Liu
Lintao Zhang
Lanshun Nie
Zhi Yang

title: Seernet: Predicting convolutional neural network feature-map sparsity through low-bit quantization

authors:
Sharan Chetlur
Cliff Woolley
Philippe Vandermersch
Jonathan Cohen
John Tran
Bryan Catanzaro
Evan Shelhamer

title: cuDNN: Efficient primitives for deep learning

venue: arXiv preprint arXiv:1410.0759,

authors:
Christopher Choy
JunYoung Gwak
Silvio Savarese

title: 4d spatio-temporal convnets: Minkowski convolutional neural networks

authors:
Marius Cordts
Mohamed Omran
Sebastian Ramos
Timo Rehfeld
Markus Enzweiler
Rodrigo Benenson
Uwe Franke
Stefan Roth
Bernt Schiele

title: The cityscapes dataset for semantic urban scene understanding

authors:
Xuanyi Dong
Junshi Huang
Yi Yang
Shuicheng Yan

title: More is less: A more complicated network with less inference complexity

authors:
Erich Elsen
Marat Dukhan
Trevor Gale
Karen Simonyan

title: Fast sparse convnets

authors:
Michael Figurnov
Maxwell D Collins
Yukun Zhu
Li Zhang
Jonathan Huang
Dmitry Vetrov
Ruslan Salakhutdinov

title: Spatially adaptive computation time for residual networks

authors:
Björn Fröhlich
Erik Rodner
Joachim Denzler

title: As time goes by—anytime semantic segmentation with iterative context forests. In Joint DAGM (German Association for Pattern Recognition) and OAGM

authors:
Benjamin Graham
Laurens van der Maaten

title: Submanifold sparse convolutional networks

venue: arXiv preprint arXiv:1706.01307,

authors:
Alex Grubb
Drew Bagnell

title: Speedboost: Anytime prediction with uniform near-optimality

venue: In Artificial Intelligence and Statistics,

authors:
Song Han
Jeff Pool
John Tran
William Dally

title: Learning both weights and connections for efficient neural network

venue: In NeurIPS,

authors:
Kaiming He
Xiangyu Zhang
Shaoqing Ren
Jian Sun

title: Deep residual learning for image recognition

authors:
Geoffrey Hinton
Oriol Vinyals
Jeff Dean

title: Distilling the knowledge in a neural network

venue: arXiv preprint arXiv:1503.02531,

authors:
Hanzhang Hu
Debadeepta Dey
Martial Hebert
J Andrew Bagnell

title: Learning anytime predictions in neural networks via adaptive loss balancing

authors:
Gao Huang
Danlu Chen
Tianhong Li
Felix Wu
Laurens van der Maaten
Kilian Q Weinberger

title: Multi-scale dense networks for resource efficient image classification

venue: arXiv preprint arXiv:1703.09844,

authors:
Benoit Jacob
Skirmantas Kligys
Bo Chen
Menglong Zhu
Matthew Tang
Andrew Howard
Hartwig Adam
Dmitry

title: Kalenichenko. Quantization and training of neural networks for efficient integer-arithmetic-only inference

authors:
Eric Jang
Shixiang Gu
Ben Poole

title: Categorical reparameterization with gumbel-softmax

venue: arXiv preprint arXiv:1611.01144,

authors:
Sergey Karayev
Mario Fritz
Trevor Darrell

title: Anytime recognition of objects and scenes

authors:
Alexander Kirillov
Yuxin Wu
Kaiming He
Ross Girshick

title: Pointrend: Image segmentation as rendering

authors:
Alex Krizhevsky
Ilya Sutskever
Geoffrey E Hinton

title: Imagenet classification with deep convolutional neural networks

venue: Communications of the ACM,

authors:
Hao Li
Asim Kadav
Igor Durdanovic
Hanan Samet
Hans Peter Graf

title: Pruning filters for efficient convnets

venue: arXiv preprint arXiv:1608.08710,

authors:
Xiaoxiao Li
Ziwei Liu
Ping Luo
Chen Change Loy
Xiaoou Tang

title: Not all pixels are equal: Difficulty-aware semantic segmentation via deep layer cascade

authors:
Ji Lin
Yongming Rao
Jiwen Lu
Jie Zhou

title: Runtime neural pruning

authors:
Yingyan Lin
Charbel Sakr
Yongjune Kim
Naresh Shanbhag

title: Predictivenet: An energyefficient convolutional neural network via zero prediction

venue: IEEE international symposium on circuits and systems (ISCAS)

authors:
Buyu Liu
Xuming He

title: Learning dynamic hierarchical models for anytime scene labeling

venue: In ECCV. Springer,

authors:
Lanlan Liu
Jia Deng

title: Dynamic deep neural networks: Optimizing accuracy-efficiency trade-offs by selective execution

venue: arXiv preprint arXiv:1701.00299,

authors:
Zhuang Liu
Mingjie Sun
Tinghui Zhou
Gao Huang
Trevor Darrell

title: Rethinking the value of network pruning

authors:
Jonathan Long
Evan Shelhamer
Trevor Darrell

title: Fully convolutional networks for semantic segmentation

authors:
Mason McGill
Pietro Perona

title: Deciding how to decide: Dynamic routing in artificial neural networks

venue: arXiv preprint arXiv:1703.06217,

authors:
Roozbeh Mottaghi
Xianjie Chen
Xiaobai Liu
Nam-Gyu Cho
Seong-Whan Lee
Sanja Fidler
Raquel Urtasun
Alan Yuille

title: The role of context for object detection and semantic segmentation in the wild

authors:
Adam Paszke
Sam Gross
Francisco Massa
Adam Lerer
James Bradbury
Gregory Chanan
Trevor Killeen
Zeming Lin
Natalia Gimelshein
Luca Antiga

title: Pytorch: An imperative style, highperformance deep learning library

venue: NeurIPS,

authors:
Mohammad Rastegari
Vicente Ordonez
Joseph Redmon
Ali Farhadi

title: Xnor-net: Imagenet classification using binary convolutional neural networks

authors:
Mengye Ren
Andrei Pokrovsky
Bin Yang
Raquel Urtasun

title: Sbnet: Sparse blocks network for fast inference

authors:
Adriana Romero
Nicolas Ballas
Samira Ebrahimi Kahou
Antoine Chassang
Carlo Gatta
Yoshua Bengio

title: Fitnets: Hints for thin deep nets

venue: arXiv preprint arXiv:1412.6550,

authors:
Mark Sandler
Andrew Howard
Menglong Zhu
Andrey Zhmoginov
Liang-Chieh Chen

title: Mobilenetv2: Inverted residuals and linear bottlenecks

authors:
Gil Shomron
Ron Banner
Moran Shkolnik
Uri Weiser

title: Thanks for nothing: Predicting zero-valued activations with lightweight convolutional neural networks

venue: arXiv preprint arXiv:1909.07636,

authors:
Ke Sun
Bin Xiao
Dong Liu
Jingdong Wang

title: Deep high-resolution representation learning for human pose estimation

authors:
Surat Teerapittayanon
Bradley McDanel
Hsiang-Tsung Kung

title: Branchynet: Fast inference via early exiting from deep neural networks

venue: In ICPR. IEEE,

authors:
Andreas Veit
Serge Belongie

title: Convolutional networks with adaptive inference graphs

venue: In ECCV, 2018

authors:
Thomas Verelst
Tinne Tuytelaars

title: Dynamic convolutions: Exploiting spatial sparsity for faster inference

authors:
Jingdong Wang
Ke Sun
Tianheng Cheng
Borui Jiang
Chaorui Deng
Yang Zhao
Dong Liu
Yadong Mu
Mingkui Tan
Xinggang Wang

title: Deep high-resolution representation learning for visual recognition

venue: IEEE transactions on pattern analysis and machine intelligence,

authors:
Xin Wang
Fisher Yu
Zi-Yi Dou
Trevor Darrell
Joseph E Gonzalez

title: Skipnet: Learning dynamic routing in convolutional networks

venue: In ECCV, 2018a

authors:
Yan Wang
Lequn Wang
Yurong You
Xu Zou
Vincent Chen
Serena Li
Gao Huang
Bharath Hariharan
Kilian Q Weinberger

title: Resource aware person re-identification across multiple resolutions

authors:
Yan Wang
Zihang Lai
Gao Huang
Brian H Wang
Laurens Van Der Maaten
Mark Campbell
Kilian Q Weinberger

title: Anytime stereo image depth estimation on mobile devices

authors:
Zuxuan Wu
Tushar Nagarajan
Abhishek Kumar
Steven Rennie
L. Davis
K. Grauman
R. Feris

title: Blockdrop: Dynamic inference paths in residual networks

authors:
Zhenda Xie
Zheng Zhang
Xizhou Zhu
Gao Huang
Stephen Lin

title: Spatially adaptive inference with stochastic feature sampling and interpolation

venue: arXiv preprint arXiv:2003.08866,

authors:
Hengshuang Zhao
Jianping Shi
Xiaojuan Qi
Xiaogang Wang
Jiaya Jia

title: Pyramid scene parsing network

authors:
Hengshuang Zhao
Xiaojuan Qi
Xiaoyong Shen
Jianping Shi
Jiaya Jia

title: Icnet for real-time semantic segmentation on high-resolution images

venue: In ECCV,

title: Using anytime algorithms in intelligent systems

venue: AI magazine,

heading: 1 INTRODUCTION

text:
Deep convolutional networks (Krizhevsky et al., 2017; He et al., 2016) achieve high accuracy but at significant computational cost. Their computational burden hinders deployment, especially for time-critical or low-resource use cases that for instance require interactivity or inference on a mobile device. This efficiency problem is tackled by special-purpose libraries (Chetlur et al., 2014), compression by network pruning (Han et al., 2015; Li et al., 2016; Liu et al., 2019) and quantization (Rastegari et al., 2016; Jacob et al., 2018), and adjusting architecture by distillation (Hinton et al., 2015; Romero et al., 2014). These solutions accelerate network computation but the entire network must still be computed; however, a prediction may be needed sooner. Time constraints vary, but the inference time of a standard deep network does not.
Anytime inference mitigates this issue by bringing flexibility to model computation. An anytime algorithm (Dean & Boddy) gradually improves its results as more computation time is given. It can by interrupted at any point during its computation to return a result as system or user requirements demand. In this way the time to the first output is reduced while the quality of the last output is preserved.
An anytime model makes a progression of predictions between the first and last. This pro-
gression continues if time remains, or halts if it is either already satisfactory or out of time. For example, consider a user on a mobile device: an approximate result could be returned earlier if there is urgency, or the user could monitor the sequence of predictions as time goes by and stop the model once it is good enough. Note that anytime inference differs from adaptive or dynamic inference
(Veit & Belongie, 2018; Wu et al., 2018; Wang et al., 2018a) where the model decides how much to compute instead of an external decision.
Prior research has explored anytime inference by feature selection (Karayev et al., 2014) or ensembling models through boosting (Grubb & Bagnell, 2012). For end-to-end models, research has focused on classification for anytime inference or adaptive inference. In particular, the multi-scale dense network (Huang et al., 2017) is an architecture for resource efficient classification. The attraction of anytime inference is not limited to classification however, and the additional computation required for pixel-level recognition tasks makes it even more desirable. For instance, an autonomous driving system may demand swifter reaction time for safety in the presence of pedestrians, and so an anytime semantic segmentor might sooner recognize their presence. In addition to urgency, an anytime segmentor could help efficiency, by not further processing already confident predictions of street pixels and therefore save power.
In this work, we develop the first single-model anytime approach for pixel-level visual recognition tasks. We adopt an early exiting framework, where multiple predictors branch off from the intermediate stages of the model. The exits are trained end-to-end (both the original exit and intermediate exits), and during inference each provides a prediction in turn. To compensate for differences in depth and spatial dimensions across stages, we redesign the predictors for earlier exits. For each exit we choose an encoder-decoder architecture that combines pooling, convolution, and interpolation to enlarge receptive fields and smooth spatial noise.
Exits might suffice for anytime image classification, but pixel-level tasks have spatial structure. Simple regions may need less processing while complex regions need more. Standard inference applies an equal amount of computation at every pixel without taking advantage of spatial structure. Spatially adaptive networks (Figurnov et al., 2017; Xie et al., 2020) improve efficiency by skipping computation in places, but unlike anytime models they only make one final prediction. We propose a spatially anytime network that makes predictions for different pixels at different points in time.
Our spatially adaptive inference scheme decides whether or not to continue computation at each exit and position. We mask the output of each exit by thresholding the confidence of its predictions: the remaining computation for sufficiently confident pixels is then reduced (Fig. 2). For each masked pixel, its prediction will be persisted in the following exits, as it is already sufficiently confident. In following layers, the features for the masked pixel will be interpolated, rather than convolved, and therefore reduce computation. The confidence measure can depend on the task, e.g., in segmentation it could be the entropy of class predictions. This confidence adaptivity can substantially reduce the total computation while maintaining accuracy.
We experiment with two pixel-level visual recognition tasks: Cityscapes semantic segmentation and MPII human pose estimation. Our networks are based on the recent HRNet architecture (Wang et al., 2020). Redesigning the exits and including confidence adaptivity significantly improves across accuracy-efficiency operating points. Our full model not only makes anytime predictions, but its final predictions achieve the same level of accuracy as the base model with 40-60% less total computation. For analysis, we visualize predictions and confidence adaptivity across exits, and ablate design choices for the exits and masking.
To summarize our contributions: (1) we propose the first general-purpose anytime inference approach for pixel-level visual recognition; (2) our redesigned exit architecture and confidenceadaptive masking boost the accuracy-efficiency tradeoff of pixel-wise anytime inference; (3) we experiment with semantic segmentation and human pose estimation to show efficacy across tasks; and (4) we analyze our design choices by visualization and ablation.

heading: 2 RELATED WORK

text:
Anytime Inference. Anytime algorithms (Zilberstein, 1996; Dean & Boddy) can be interrupted at any point during computation to return a result, whose quality improves gradually with more computation time. In machine learning, anytime inference has been achieved by boosting (Grubb & Bagnell, 2012), reinforcement learning (Karayev et al., 2014), and random forests (Fröhlich et al., 2012). Anytime deep networks have been brought to bear on image recognition, but not pixel-level recognition. Branching architectures have been a common strategy (Amthor et al., 2016; Teerapittayanon et al., 2016) along with other techniques such as adaptive loss balancing (Hu et al., 2019).
While there is work on the tasks of person re-identification (Wang et al., 2019) and stereo depth (Wang et al., 2018b), these techniques are task specific, while our method applies to multiple pixellevel tasks, as we show with semantic segmentation and pose estimation. Liu et al. (Liu & He, 2016) learn a hierarchy of models for anytime segmentation, but its multiple models complicate training and testing, and require more memory. Our work instead augment the base model architecture for simplicity and efficiency. The PointRend method (Kirillov et al., 2020) outputs a initial dense prediction first and then refine it adaptively, but the predictions are all made at full depth. Its majority of the computation is spent before the first output and thus cannot be practically “anytime”. Our method is the first to selectively update anytime predictions across space and layers.
Adaptive Computation. An adaptive model adjusts its computation to each specific instance during inference. For deep networks, this is often done by adjusting which layers to execute, that is, choosing which layers to run or skip. This can be done by a supervised controller (Veit & Belongie, 2018; Liu & Deng, 2017), a routing policy optimized by reinforcement learning (Wang et al., 2018a; Wu et al., 2018; Lin et al., 2017a), or other training strategies (McGill & Perona, 2017). Rather than choosing layers, spatial adaptivity chooses where to adjust the amount of computation across different spatial positions in the input. For example, the model could infer spatial masks for feature maps and skip computation on masked areas (Shomron et al., 2019; Dong et al., 2017; Lin et al., 2017b; Ren et al., 2018; Cao et al., 2019). Figurnov et al. (2017) maintains a halting score at each pixel and once it reaches a threshold the model will stop inference at those positions for spatially coarse tasks like classification or bounding box detection. Xie et al. (2020) stochastically sample positions for computation from an end-to-end learned sampling distribution. Li et al. (2017) convert a deep network into a difficulty-aware cascade, where earlier steps handle easier regions and later steps tackle harder regions. These spatially adaptive models reduce computation, but are not anytime: they do not make a series of predictions and cannot be interrupted.

heading: 3 APPROACH

text:
Anytime Setting and the Early Exiting Framework. In an anytime inference setting, the user can stop the inference process based on the input or a current event. Thus the computation budget for each instance x could be time or input dependent. We use B(x, t) to denote the computation budget assigned for instance x at time t, where the time variable t models events that can change the budget. B(x, t) could be independent of x, i.e., the budget only depends on the time t, for example if a model on a server is asked to make predictions with less budget during high-traffic hours; B(x, t) can also be independent of t, meaning the budget is only decided by input x, regardless of external events. The output of the anytime model depends on the budget given, and we denote it as f(x,B(x, t)). Assuming L is the task loss and y is the ground truth, the per-instance loss is L(f (x,B (x, t)) , y). This leads to the expected training loss to be E(x,y)∼(X,Y ),t∼T [L(f (x,B (x, t)) , y)], where (X,Y ) is the input-output joint distribution and T is the distribution modeling the time or event variable.
Next, we introduce the early exiting framework which have been used in prior works (Huang et al., 2017; Teerapittayanon et al., 2016) for anytime prediction. Standard convolutional networks only have one prediction “head” at its final stage. The network takes the input x, forwards it through intermediate layers, and finally output the prediction at its head. The concrete form of the head depends on the task. For pixel-level recognition, the head is usually one or multiple convolutions that output spatial maps representing pixel-wise predictions.
To obtain an anytime model, we attach multiple heads to the network, branching from its intermediate features (Fig. 2). We call these additional heads early exits, since they allow the network to give early predictions and stop the inference at the current layer. Suppose we add k early exits at intermediate layers with layer indices l1 . . . , lk. We denote the intermediate features at these layers Fl1(x) . . . , Flk(x), and the functions represented by the early exits E1 . . . , Ek. Note that Eis may be of the same form but they do not share weights. The early prediction maps can be denoted as ŷi = Ei(Fli(x)), i = 1 . . . k. Together with the original final prediction ŷk+1, the total loss is:
Ltotal = k+1∑ i=1 wiL(ŷi, y) (1)
where wi is the weight coefficient at exit i. The original network, together with the added exits, will be trained end-to-end to optimize this total loss function. In experiments, we set all weights equal to
1. This corresponds to the minimization of the expected loss in Sec. 3 when the exiting probabilities at all exits are equal. We find this to be a simple yet effective scheme.
For anytime inference, as the network propagates features through its layers, if the computation budget is reached or the user asks the model to stop, it will output the latest ŷi that is already computed. Similar early exiting strategies have been used in resource-efficient image classification (Teerapittayanon et al., 2016; Huang et al., 2017), but pixel-level recognition requires further steps detailed in the following subsections.
Head Redesign. Typical convolutional networks have a hierarchical structure that begins with shallow, fine, and more local features and ends with deep, coarse, and more global features. These deeper features represent more image content by their larger receptive fields. For pixel-level tasks, upsampling is done within the network to restore lost resolution during downsampling, and ensure precise spatial correspondence between the input and the output. This upsampling can be accomplished in few (Long et al., 2015) or many (Zhao et al., 2017) layers, but no matter the architecture, the network learns its most local features in its earliest layers. This presents a challenge for the earliest exits, since these features are limited in depth and receptive field. Making direct predictions at these exits with the typical 1×1 convolution head produces spatially noisy and inaccurate results. To compensate for these lacking early features, we redesign the prediction heads for the exits Ei. Each Ei first downsamples its input features Fli(x), through a series of pooling and 1×1 convolution layers. Each pooling operation halves the spatial resolution, increasing its output’s receptive fields. The following convolution provides the opportunity to learn new coarser-level features, specifically for that exit’s prediction. After several (denoting this number as D) “pool-conv” layers, we upsample the features back to the original output resolution, with an equal number (D) of bilinear interpolation and 1× 1 convolution layers. The output of this “interpolate-conv” sequence will be the prediction ŷi at this exit. This is important for ensuring the spatial accuracy of the prediction for pixel-level tasks. Our redesigned exits are essentially small “encoder-decoder” modules (Fig. 2), where the encoder downsamples the features, the decoder upsamples them back.
The downsampling ratio at each exit is determined by D, the number of consecutive “pool-conv” layers. Intuitively, features at earlier layers are more fine-level, and the exit branching from them can potentially benefit from more downsampling. In experiments, we use encoder with D = N − i downsampling operations at exit i, where N is the total number of exits, including the original last exit. Empirically we find this strategy works well, and alternative strategies are compared in Sec. 5.
Finally, in all early exits, the first convolution will transform the number of channels to a fixed number for all exits. By setting the channel width relatively small, we can still save computation while adding layers with this redesigned encoder-decoder head structure.
Confidence Adaptivity. For pixel-level recognition tasks, any early prediction ŷi is a spatial map consisting of pixel-wise predictions at each position. While most convolution networks spend equal amount of computation at each input position, it is likely that recognition at some regions are easier than others, where the network can make predictions with a high confidence even at earlier exits. For instance, the inner part of a large sky segment may be easy to recognize, whereas the boundary between the bicycle and the person riding it may need more careful delineation.
Once an early prediction is made, we can inspect the “confidence” at each position. As an example, for semantic segmentation, the maximum probability over all classes can serve as a confidence measure. If the confidence has passed a pre-defined threshold at certain positions (green squares on predictions in Fig. 2), we may decide these predictions are likely to be correct, and not continue the computation of further layers at this position. Suppose the pixels of the early prediction ŷi are indexed by p, we form a mask Mi:
Mi(p) = { 0, if Confidence(ŷi(p)) ≥ Threshold 1, otherwise
(2)
For any convolution layer between exit i (Ei) and the next exit i + 1 (Ei+1), we could choose whether to perform or skip computation at position p based on the mask (Fig. 2). Assuming C is a convolution layer with input fin, then by applying the mask, the output fout at position p becomes:
fout(p) = { C(fin)(p), if Mi(p) = 1, 0, if Mi(p) = 0.
(3)
If C’s output and the mask Mi do not share the same spatial size, we interpolate ŷi in Eqn. 2 to the size of C’s output, so that the mask Mi is compatible with C in Eqn. 3.
The output fout could be sparse, with many positions being 0. This could potentially harm further convolutional computation. To compensate for this, we spatially interpolate these positions from their neighbors across all channels, using a similar approach as in (Xie et al., 2020). Denoting the interpolation operation as I , the final output feature f∗out is
f∗out(p) = { fout(p), if Mi(p) = 1, I(fout)(p), if Mi(p) = 0.
(4)
Here, the value of I(fout)(p) is a weighted average of all the neighboring pixels centered at p within a radius r:
I(fout)(p) =
∑ s∈Ω(p) W(p,s)fout(s)∑
s∈Ω(p) W(p,s) (5)
where s indexes p’s neighboring pixels and Ω(p) = {s|∥s− p∥∞ ≤ r, s ̸= p}, the neighborhood of p. We set radius r = 7 in our experiments. W(p,s) is the weight assigned to point s for interpolating at p, for which we use the RBF kernel, a distance-based exponential decaying weighting scheme:
W(p,s) = exp (−λ2∥p− s∥22) (6) with λ being a trainable parameter. This indicates that the closer s is to p, the larger its assigned weight will be. Note that masked-out features (Mi(p) = 0) still participate in the interpolation process as inputs with values of 0.
Replacing filtering by interpolation at these already confident spatial locations (Mi(p) = 0) could potentially save a substantial amount of computation. The mask Mi will be used for all convolutions between exit i and i+ 1, including the convolutions inside exit i+ 1. Once the forward pass arrives at the next exit, to make the prediction ŷi+1, the last prediction at positions where Mi(p) = 0 will be carried over, having already been deemed confident enough at the last exit and having been skipped during further computations. This means:
ŷi+1(p) = { Ei+1(Fli+1(x)), if Mi(p) = 1, ŷi(p), if Mi(p) = 0.
(7)
The network then calculates a new mask Mi+1 based on ŷi+1, and uses it to skip computation going forward. The process continues until we reach the final exit.
In summary, we incorporate spatial confidence adaptivity into the early exiting network, by not filtering at spatial locations that are already sufficiently confident in the latest prediction. At these positions interpolation is used instead, at much reduced computational cost, to avoid excessive sparsity. Unless otherwise specified, confidence adaptivity is used in both training and inference.

heading: 4 EXPERIMENTS

text:
We evaluate our approach with two pixel-level visual recognition tasks: semantic segmentation and human pose estimation. Our experiments are implemented using PyTorch (Paszke et al., 2019), and our code is available at https://github.com/anonymous20202020/anytime.
Architectures. We use the High-Resolution Network (HRNet) (Wang et al., 2020) architecture as our base model. HRNet is a multi-stage architecture, where each stage adds lower-resolution/largerscale features. Specifically, we adopt the standard HRNet-{W48,W32} models and the smaller HRNet-W18 model. HRNet-W48 is state-of-the-art for semantic segmentation and HRNet-W32 is suitable for pose estimation. HRNet-W18 is highly efficient and has been shown to outperform other efficient networks (Zhao et al., 2018; Sandler et al., 2018) in its accuracy-efficiency tradeoff. The 48/32/18 denotes the number of channels in the bottleneck of the first stage. The original head for HRNet before our redesigning is two consecutive 1 × 1 convolutions. We attach three exits, one at the end of each stage before the final prediction. We follow the training/evaluation protocol and hyperparameters of the reference HRNet implementation at (Sun et al., 2019; Wang et al., 2020) (except that our models include a loss at each exit). Please see Appendix E for more training details.
Baselines. 1. HRNet: we compare with a standard HRNet that has only one (final) exit with the same backbone architecture. The standard HRNet is not anytime, so we focus on comparing it with our anytime model’s final exit. 2. MDEQ (Bai et al., 2020) is a recent deep implicit model, which achieves competitive performance on vision tasks without stacking explicit layers, but rather solves an optimization problem for inference. Its representation z∗ is an equilibrium point of its learned transformation f(z;x), i.e., f(z∗;x) = z∗ where x is the input. The representation is obtained by iteratively solving the equation f(z;x) = z, for which the quality of the solution improves with more iterations. The converged representation is then decoded into a prediction. We examine anytime prediction with the MDEQ by decoding intermediate iterates of the representation. To the best of our knowledge this is the first study of anytime implicit modeling, as (Bai et al., 2020) only report the predictions of implicit models at equilibrium, and do not produce or inspect intermediate predictions. We use the “small” version of the MDEQ (Bai et al., 2020) and the 4th, 6th, 8th, and 10th iterations of its equilibrium optimization to bound the amount of computation and align its iterations with our architecture’s stages. 3. Feature-Based Stochastic Sampling: we follow Xie et al. (2020) in using internal features to predict masking positions, with the Gumbel-Softmax trick (Jang et al., 2016) used for sampling. We use a 3 × 3 convolution upon the features for exits (Fig. 2) for mask prediction until the next exit. During training, an L1 sparsity regularization is applied on the stochastic continuous mask values and only during inference the mask values are discretized. The interpolation procedure is the same as in our method. This baseline is evaluated on HRNet-W18.

heading: 4.1 SEMANTIC SEGMENTATION

text:
The Cityscapes dataset (Cordts et al., 2016) consists of 2048×1024 images of urban street scenes with segmentation annotations of 19 classes. We train the models with the training set and report results on the validation set. The accuracy metric is the standard mean intersection-over-union (mIoU %), and the computation metric is the number of floating point operations (FLOPs). Anytime inference improves with higher accuracy, less computation, and more predictions. We evaluate HRNet-W48 and HRNet-W18 for this task.
Redesigned heads (RH) uses our encoder-decoder structure for exits. Since we have 4 exits in total, we repeat the downsampling operation 3/2/1 times at exit 1/2/3 to generate larger-scale features for earlier exits, as described in Sec. 3. We set the number of channels at all exits to 128/64 for HRNet-W48/W18. For confidence adaptivity (CA), we use the maximum probability among all classes as the confidence measure, and set the confidence threshold in Eqn. 2 to be 99.8% based on cross validation. For CA, the computation for each input can differ, so we report the average FLOPs across all validation images at each exit.
The results for HRNet-W48 are shown in Table 1. We observe that our early exiting model based on HRNet-W48 outperforms the MDEQ model by a large margin, with significantly less FLOPs at each exit. With RH, we achieve notable accuracy gain in early predictions, especially at the first exit (more than 10%), with roughly the same computation. With CA added, we arrive at our full model (RH + CA), which maintains roughly the same accuracy as the RH model but reduces the
total computation at exits 3 and 4. Interestingly our full RH + CA model has slightly higher mIoU at the final exit (81.3 vs. 80.7) with 44.4% less total computation (387.1 vs. 696.2 GFLOPs) compared to the base HRNet. This is possibly due to a potential regularization effect of confidence adaptivity: computing fewer intermediate features exactly may prevent overfitting.
The same results are plotted in Fig. 3 (left). The plot shows accuracy (y-axis) and computation (xaxis) tradeoffs: points to the upper left indicate better anytime performance. The baseline HRNet is represented by a red cross, while anytime models are plotted as curves with a point for each prediction. We plot the results for the smaller HRNet-W18 model in Fig. 3 (middle). RH improves early prediction accuracy from the basic early exiting model, and CA substantially reduces computation at later exits. The full model reaches the same-level accuracy as the baseline HRNet with much less total computation. We note that our model with confidence values as mask indicators also outperforms the feature-based mask sampling method in accuracy-computation tradeoff, demonstrate that confidence is effective at filtering out redundant computation despite its simplicity.
Our experiments measure computation by FLOPs rather than time. Reporting FLOPs is common (Figurnov et al., 2017; Xie et al., 2020; Huang et al., 2017; Wang et al., 2018a; Liu et al., 2019) and meaningful because it is hardware independent. However, similarly to spatially adaptive computation methods (Figurnov et al., 2017; Xie et al., 2020), our model does not achieve wall clock speedup at this time due to the lack of software/hardware support for sparse convolution with current frameworks and GPU devices. To approximate CPU speedup, we conduct a profiling experiment on a multi-threading processor (specifically we measure computation time on a Linux machine with Intel Xeon Gold 5220R CPUs using 16 threads). We replace all convolutions with our implementations following (Xie et al., 2020). Our full (RH + CA) based on HRNet-W48 achieves 1.48× speedup compared to the non-anytime baseline, measured in end-to-end latency (wall-clock time). There is a gap between this measured time and the theoretical 1.80× speedup measured by FLOPs. Our approach and others can benefit from ongoing and future work on efficient sparse convolutions (Graham & van der Maaten, 2017; Choy et al., 2019; Verelst & Tuytelaars, 2020; Elsen et al.,
2020). Please see the supplement for an anytime inference video where each exit is timed to the computation it requires.

heading: 4.2 HUMAN POSE ESTIMATION

text:
For human pose estimation we evaluate on the MPII Human Pose dataset (Andriluka et al., 2014) of image crops annotated with body joints collected from everyday human activities. The positions of 16 joint types are annotated for the human centered in each crop. We report the standard metric (Andriluka et al., 2014) for MPII, the PCKh (head-normalized probability of correct keypoint) score, on its validation set. We use HRNet-W32 for this task and follow the reference settings from (Sun et al., 2019). The standard head for this task is 1×1 convolution. As in segmentation, our redesigned heads are encoder-decoder structures. The number of channels for all exits is 64.
Pose estimation task is formulated as regression. The HRNet model outputs 16 spatial feature maps, each one regressing the corresponding body joint. The only positive target for each type is coded as 1; all other points are negatives coded as 0. Unlike in segmentation, the output at each pixel is not a probability distribution, so we use the maximum value across channels as the confidence measure. A pixel is masked out if the maximum value at that position is smaller than the threshold, marking it unlikely to be a joint prediction. We choose 0.002 as the threshold by cross validation, as a larger value makes the mask too sparse and hurts learning. The RH + CA model adopts adaptivity after 10 epochs of normal training, because nearly all outputs are too close to zero in the beginning.
Fig. 3 (right) and Table 2 show the results. We observe a similar trend to segmentation: RH improves accuracy and CA reduces FLOPs. In this case, our full model reduces computation by 59.1% (9.49 to 3.88 GFLOPs) while accuracy only drops by 0.13% relative to the baseline HRNet.

heading: 5 ANALYSIS

text:
In this section, we visualize predictions and confidence values at each exit to gain a better understanding of the confidence adaptivity. We also conduct ablation studies on important aspects of our design choices. The experiments are done on Cityscapes segmentation.
Visualizations. To inspect our anytime predictions and masking, we visualize exits on a validation image with HRNet-W48 (RH + CA). Fig. 4 shows the predictions, confidence maps, and computation masks across exits. With each exit, the prediction accuracy improves, especially in more detailed areas with more segments. The confidence maps are shown with high lighter/yellow and low darker/green. Most unconfident points lie around segment boundaries, and the interior of large stuff segments (road, vegetation) are already confident at early exits. This motivates the use of confidence adaptivity to avoid unnecessary further computations on these areas. For computation masks, the correct/incorrect predictions at each exit are marked white/black. Pixels surpassing the confidence threshold (99.8%) are masked and marked green. Many pixels can be masked out in this way, and each exit masks more. Most of masked pixels are found in inner parts of large segments or in already correct areas. In fact, the masked pixels are 100% correct at all exits for this instance, which partly justifies their exclusion from later computation. The predictions at these positions are already confident and correct at early exits, and so the only potential harm of skipping their computation later is their possible effect at less confident positions. See Appendix G for more visualizations. On average, 19.3%, 38.4%, 63.0% pixels are masked out at exit 1, 2, 3, respectively.
Downsampling at Early Exits. In Sec. 3, we described how many consecutive downsampling operations we use at each exit, by D = N − i, which means we use D = 3/2/1 consecutive “pool-
conv” layers for downsampling at exit 1/2/3. Here we compare this strategy with D = 1/1/1 and 3/3/3, where the same level of downsampling and hence the same head structure is used at all exits, on HRNet-W18. Fig. 5 (left) shows that our adopted D = 3/2/1 strategy obtains the highest accuracy at all exits among these choices.
Masking Criterion. We used the max probability as the confidence measure and a fixed threshold for masking. Here we consider a few alternatives. One is to mask out the top k% (by max prob.) of the pixels at each exit, regardless of their values. We also consider thresholding on the entropy of the probability distribution. In addition, we compare them with random masking. We use HRNet-W18, change the ratio or threshold for a wide range, and present the average mIoU vs. GFLOPs on all exits at Fig. 5 (right). For this ablation, adaptivity is only applied during inference.
First we notice all three confidence criteria largely outperform random masking. For max probability, using a threshold performs slightly better than a fixed ratio, possibly because this gives the flexibility for different exits to mask out different amount of points. Finally we observe using entropy as the confidence measure performs similarly as using max probability, but we stick to max probability in our methods because it is trivial to compute.

heading: 6 CONCLUSION

text: We propose the first single-model anytime approach for pixel-level visual recognition. Based on an early-exiting framework, our redesigned exiting heads and confidence adaptivity both improve the accuracy-computation tradeoff. On Cityscapes semantic segmentation and MPII pose estimation, our approach achieves 40%-60% FLOPs reduction with the same-level final accuracy, compared against the baseline HRNet. We further analyze confidence adaptivity with visualizations and ablate key design choices to justify our anytime inference approach.

heading: A ABLATION ON INTERPOLATION RADIUS

text:
In the main paper, we use a default radius of r = 7 when interpolating masked-out features (Eqn. 6 and following text). Here we demonstrate that the radius of 7 is a reasonable through an ablation experiment, whose results are listed in Table 3. The experiment is conducted with HRNet-W18 on Cityscapes semantic segmentation, with both redesigned head (RH) and confidence adaptivity (CA). We observe that a radius of 7 outperforms lower ones (3 and 5) in the average mIoU slightly, with minimal FLOPs addition, due to the fact that interpolation is done channel-wisely. A further increase of radius to 9 does not bring significant gain in final or average mIoU.
B INFERENCE-ONLY CONFIDENCE ADAPTIVITY
In the experiment section of the main paper, confidence adaptivity is used at both training and inference. Here we compare this with the setting where adaptivity is only used for inference in Table 4. We use HRNet-W48 with redeisgned heads (RH) on Cityscapes for this experiment. “No Adaptivity” corresponds to the “Early Exiting (RH)” row in Table 1. We observe that using adaptivity only at inference hurts the accuracy, compared with using it at both training and inference. It also increases the average FLOPs at exit 3 and 4.

heading: C PASCAL-CONTEXT SEMANTIC SEGMENTATION RESULTS

text:
We present results with the PASCAL-Context semantic segmentation dataset (Mottaghi et al., 2014) in Table 5. It consists of 59 segmentation classes. For the Early Exiting baseline, we use weights of (0.33, 0.33, 0.33, 1) for 4 exits, respectively, as we found increasing it to all 1 would hurt the final performance too much. The confidence threshold is set to 99.5%. We observe RH improve the accuracy in most exits. Our full approach (RH+CA) outperforms the Early Exiting baseline in average mIoU, despite its final mIoU is worse. It also saves more than 20% FLOPs compared with the vanilla Early Exiting baseline.
D VIDEO DEMO
A video demonstration of anytime prediction is included in the supplement (demo.mp4). The anytime model used is an early exiting HRNet-W48 with RH (redesigned heads) + CA (confidence
adaptivity). The predictions of the anytime model are timed in proportion to the amount of computation required. Our anytime model is able to output reasonable result much earlier compared with the conventional model. Its also outputs the final result with almost half of computations as the conventional model, with similar visual quality.

heading: E TRAINING DETAILS

text:
For Cityscapes semantic segmentation, we follow the training settings at the official codebase (hrn, 2019b) of HRNet for semantic segmentation. The HRNet-W18/48 models are pretrained on ImageNet. During training, multi-scale and flipping data augmentation is used, and the input cropping size is 512 × 1024. The model is trained for 484 epochs, with a initial learning rate of 0.01 and a polynomial schedule of power 0.9, a weight decay of 0.0005, a batch size of 12, optimized by SGD with 0.9 momentum. In evaluation, we use single-scale testing without flipping, with input resolution 1024 × 2048. For the Feature-Based Stochastic Sampling baseline, we modify the exit weights from (1, 1, 1, 1) to (0.5, 0.5, 0.5, 1) as we find it produces more stable masking values during training. The L1 sparsity regularization on masks is set to 0.1. The mask outputs at exit (1, 2, 3) have additional weight factors of (1/3, 2/3, 1) to encourage more sparse features towards the end.
For MPII human pose estimation, we follow the training settings at the official codebase (hrn, 2019a) of HRNet for pose estimation. The HRNet-32 model we use is also pretrained on ImageNet. The image size for both training and evaluation is 256× 256. The model is trained for 210 epochs, with a initial learning rate of 0.001, and a decaying of 0.1 at epoch 170 and 200. The optimization is done by Adam with γ1 = 0.99, γ2 = 0, a weight decay of 0.0001, and a momentum of 0.9. The batch size is 128. In evaluation, flipping test is used.

heading: F MORE MDEQ RESULTS

text: In the main paper, we used MDEQ’s “small” model’s 4th, 6th, 8th and 10th iterations’ results to align with our model’s 4 exits. In this sectioin, we provide full results on Cityscapes semantic segmentation at all iterations for both the “small” and the “XL” (extra-large) models at Table 6. The original configuration (mde, 2020) sets the number of iterations to 26 and 27 for MDEQ-small and MDEQ-XL. In Fig. 9 and 10, we also provide qualitative visualization of results for the same 6 validation images from Fig. 6, with MDEQ-small at 4th, 6th, 8th, 10th, 14th, 18th, 22th, 26th iterations. We observe that with the progression of iterations, the predictions get more and more accurate.

heading: G MORE VISUALIZATIONS

text: We present more visualizations of the same type as Fig. 5 in the main paper, in Fig. 7 and 8. Their input and ground truth are shown in Fig. 6 in the same order. We can see the same trend as discussed in the main paper still holds: the model will mask out confident points that are inside large segments (e.g., road, vegetable), which are mostly already predicted correctly in early exits.