TIPS: Topologically Important Path Sampling for Anytime Neural Networks
Anytime neural networks (AnytimeNNs) are a promising solution to adaptively
adjust the model complexity at runtime under various hardware resource
constraints. However, the manually-designed AnytimeNNs are biased by designers'
prior experience and thus provide sub-optimal solutions. To address the
limitations of existing hand-crafted approaches, we first model the training
process of AnytimeNNs as a discrete-time Markov chain (DTMC) and use it to
identify the paths that contribute the most to the training of AnytimeNNs.
Based on this new DTMC-based analysis, we further propose TIPS, a framework to
automatically design AnytimeNNs under various hardware constraints. Our
experimental results show that TIPS can improve the convergence rate and test
accuracy of AnytimeNNs. Compared to the existing AnytimeNNs approaches, TIPS
improves the accuracy by 2%-6.6% on multiple datasets and achieves SOTA
accuracy-FLOPs tradeoffs.
Guihong Li, Kartikeya Bhardwaj, Yuedong Yang, Radu Marculescu
# TIPS: Topologically Important Path Sampling for Anytime Neural Networks

###### Abstract

Anytime neural networks (AnytimeNNs) are a promising solution to adaptively adjust the model complexity at runtime under various hardware resource constraints. However, the manually-designed AnytimeNNs are biased by designers' prior experience and thus provide sub-optimal solutions. To address the limitations of existing hand-crafted approaches, we first model the training process of AnytimeNNs as a discrete-time Markov chain (DTMC) and use it to identify the paths that contribute the most to the training of AnytimeNNs. Based on this new DTMC-based analysis, we further propose _TIPS_, a framework to automatically design AnytimeNNs under various hardware constraints. Our experimental results show that TIPS can improve the convergence rate and test accuracy of AnytimeNNs. Compared to the existing AnytimeNNs approaches, TIPS improves the accuracy by 2%-6.6% on multiple datasets and achieves SOTA accuracy-FLOPs tradeoffs.

Machine Learning, ICML, ICML

## 1 Introduction

In recent years, deep neural networks (DNNs) have been successful in many areas, such as computer vision or natural language processing (Vaswani et al., 2017; Dosovitskiy et al., 2021). However, the intensive computational requirements of existing large models limit their deployment on resource-constrained devices for Internet-of-Things (IoT) and edge applications. To improve the hardware efficiency of DNNs, multiple techniques have been proposed, such as quantization (Qin et al., 2020; Han et al., 2016), pruning (Luo et al., 2017; Han et al., 2015), knowledge distillation (Hinton et al., 2015), and neural architecture search (NAS) (Zoph & Le, 2017; Liu et al., 2019; Stamoulis et al., 2019; Li et al., 2020; 2023). We note that all these techniques focus on generating _static_ neural architectures that can achieve high accuracy under specific hardware constraints.

Recently, anytime neural networks (AnytimeNNs) have been proposed as an orthogonal direction to static neural networks (Huang et al., 2018; Yu & Huang, 2019; Bengio et al., 2015; Wang et al., 2021; Yang et al., 2021). AnytimeNNs adjust the model size at runtime by selecting sub-networks from a static supernet (Chen et al., 2019; Li et al., 2019; Yu & Huang, 2019; Yu et al., 2019). Compared to the static techniques, AnytimeNNs can automatically adapt (at runtime) the model complexity based on the available hardware resources. However, the existing AnytimeNNs are manually designed by selecting a few candidate subnetworks. Hence, such hand-crafted AnytimeNNs are likely to miss the subnetworks that can offer better performance. These limitations of existing manual design approaches motivate us to analyze the properties of AnytimeNNs and then provide a new algorithmic solution. Specifically, in this work, we address two **key questions:**

1. _How can we quantify the importance of various operations (e.g., convolutions, residual additions, etc.) to the convergence rate and accuracy of AnytimeNNs?_
2. _Are there topological (i.e., related to network structure) properties that can help us design better AnytimeNNs?_

To answer these questions, we analyze the AnytimeNNs from a _graph theory_ perspective. This idea is motivated by the observation that the topological features of DNNs can accurately indicate their gradient propagation properties and test performance (Bhardwaj et al., 2021; Li et al., 2021). Inspired by the network structure analysis, given an AnytimeNN, we propose a Discrete-Time Markov Chain (DTMC)-based framework to explore the relationships among different subnetworks. We then propose two new topological metrics, namely _Topological Accumulated Score_ (TAS) and _Topological Path Score_ (TPS) to analyze the gradient properties of AnytimeNNs. Based on these two metrics, we finally propose a new training method, _i.e., Topologically Important Path Sampling_ (TIPS), to improve the convergence rate and test performance of AnytimeNNs. The experimental results show that our proposed approach outperforms SOTA approaches by a significant margin across
many models and datasets (see Fig. 1). Overall, we make the following **key contributions:**

* We propose a new importance analysis framework by modeling the AnytimeNNs as DTMCs; this enables us to capture the relationships among different subnetworks of AnytimeNNs.
* Based on the DTMC-based framework, we propose two new topological metrics, _Topological Accumulated Score_ (TAS) and _Topological Path Score_ (TPS), which can characterize the operations that contribute the most to the training of AnytimeNNs.
* We propose a new theoretically-grounded training strategy for AnytimeNNs, namely, _Topologically Important Path Sampling_ (TIPS), based on our importance analysis framework. We show that TIPS achieves a faster convergence rate compared to SOTA training methods.
* We demonstrate that TIPS enables the automatic design of better AnytimeNNs under various hardware constraints. Compared to existing AnytimeNN methods, TIPS improves the accuracy by 2%-6.6% and achieves SOTA accuracy-FLOPs tradeoffs on multiple datasets, under various hardware constraints (see Fig. 1).

The rest of the paper is organized as follows. In Section 2, we discuss related work. In Section 3, we formulate the problem and introduce our proposed solution (TIPS). Section 4 presents our experimental results and outline directions for future work. Finally, Section 5 concludes the paper.

## 2 Related Work

There are three major directions related to our work:

### Anytime Inference

Anytime neural networks (AnytimeNNs) can adapt the model complexity at runtime to various hardware constraints; this is achieved by selecting the optimal subnetworks of a given (static) architecture (_supernet_), while maintaining the test accuracy. The runtime adaptation of AnytimeNNs is primarily driven by the available hardware resources (Yuan et al., 2020). For instance, early-exit networks can stop the computation at some intermediate layers of the supernet and then use individual output layers to get the final results (Wang et al., 2018; Veit and Belongie, 2018; Bolukbasi et al., 2017). Similarly, skippable networks can bypass several layers at runtime (Wang et al., 2020; Larsson et al., 2017; Wu et al., 2018). Alternatively, approaches for slimmable networks remove several channels of some layers at runtime (Lee and Shin, 2018; Bejnordi et al., 2020; Yang et al., 2018; Hua et al., 2019; Li et al., 2021; Chin et al., 2021; Gao et al., 2019; Tang et al., 2021). Finally, multi-branch networks select the suitable branches of networks to reduce the computation workload to fit the current hardware constraints (Cai et al., 2021; Ruiz and Verbeek, 2021; Huang et al., 2018; Liu et al., 2020).

### Layerwise Dynamical Isometry (LDI)

LDI is meant to quantify the gradient flow properties of DNNs (Saxe et al., 2014; Xiao et al., 2018; Burkholz and Dubatovka, 2019). For a deep neural network, let \(x_{i}\) be the output of layer \(i\); the Jacobian matrix of layer \(i\) is defined as: \(J_{i,i-1}=\frac{\partial x_{i}}{\partial x_{i-1}}\). Authors of (Lee et al., 2020) show that if the singular values of \(J_{i,i-1}\) for all \(i\) at initialization are close to 1, then the network satisfies the LDI, and the magnitude of the gradient does not vanish or explode, thus benefiting the training process.

### Network Topology

Previous works show that the topological properties can significantly impact the convergence rate and test performance of deep networks. For example, by modeling deep networks as graphs, authors in (Bhardwaj et al., 2021) prove that the average node degrees of deep networks are highly correlated with their convergence speeds. Lately, (Chen et al., 2022) developed a similar understanding of neural networks' connectivity patterns on its trainability. Moreover, several works also show that some specific topological properties of deep networks can indicate their test accuracy (Li et al., 2021; Javaheripi et al., 2021). We note that these existing approaches primarily focus on networks with a static structure. The relationship between topological properties and the convergence/accuracy of networks with varying architectures (_e.g._, AnytimeNNs) remains an open question. This motivates us to investigate the topological properties of AnytimeNNs.

## 3 Approach

In this work, for a given deep network (_i.e._, supernet), our goal is to automatically find its AnytimeNN version under

Figure 1: Test Accuracy vs. FLOPs on ImageNet. TIPS achieves higher accuracy (given the same or even fewer FLOPs) than SOTA AnytimeNNs: Joslim (Chin et al., 2021) and US-Nets (Yu and Huang, 2019).
various hardware constraints. To this end, our approach consists of three major steps: (_i_) Characterize the importance of each operation (convolution, residual addition, _etc._). As such, we model the training process of AnytimeNNs as a DTMC and use it to analyze their topological properties (Fig. 2). (_ii_) Based on this importance analysis, we then propose a new training strategy (TIPS) to improve the accuracy of AnytimeNNs. (_iii_) Finally, we search for the AnytimeNNs under various hardware constraints. Next, we discuss these steps in detail.

### Modeling AnytimeNNs as Markov Chains

#### 3.1.1 Modeling AnytimeNNs as Graphs

As shown in Fig. 2(a), we model various DNN operations (convolutions, residual additions, _etc._) as _edges_, and model the outputs of such operations (_i.e._, featuremaps) as _nodes_ in a graph. This way, a given architecture (supernet) is represented by a static undirected graph \(G=(V,E)\), where \(V\) is the set of nodes (with \(|V|=N\)) and \(E\) is the set of edges between nodes (with \(|E|=M\)). For a given DNN architecture, its corresponding AnytimeNNs select suitable subnetworks under the current hardware constraints. Specifically, these _subnetworks_\(G_{k}\) are obtained by sampling edges from the initial supernet \(G\):

\[G_{k}=(V,E_{k}),E_{k}\subseteq E \tag{1}\]

where, the node set \(V\) is the same for all subnetworks, but different subnetworks \(G_{k}\) have different edge sets \(E_{k}\) (see Fig. 2(a)). To ensure that the sampled subnetwork is valid, we always sample the input, output, and down-sample layers (_e.g._, layers with pooling or stride=2). To ensure the validity of a subnetwork, we first randomly decide whether or not each layer remains in the subnetwork. For the remaining layers, we also ensure that #channels in consecutive layers match. As shown in Fig. 2(a), based on the topology of \(G_{k}\), we can construct the adjacency matrix \(\mathbf{A}_{k}\in R^{N\times N}\) for a subnetwork as follows:

\[\begin{cases}\mathbf{A}_{k}(s,t)=0,&\text{if }(s,t)\notin E_{k}\\ \mathbf{A}_{k}(s,t)=1,&\text{if }(s,t)\in E_{k}\\ \mathbf{A}_{k}(s,t)=1,&\text{if }s=t=1\text{ or }s=t=N\end{cases} \tag{2}\]

where each edge \((s,t)\) corresponds to an operation in the given network. The intuition behind the values of \(\mathbf{A}_{k}(1,1)\) and \(\mathbf{A}_{k}(N,N)\) is that the computation always starts from the input/output layer in the forward/backward path. We note that our objective is to analyze the _layer-wise_ gradient properties of AnytimeNNs. Since the singular values of each layer's Jacobian are designed to be around 1 by commonly used initialization schemes (_e.g._, by maintaining uniform gradient variance at all layers), it is reasonable to assign '1' as the weight of each edge (_i.e._, operation) in Eq. 2 if it appears in \(A_{k}\). More details are given in Appendix C.

Figure 2: Overview of our proposed DTMC-based analysis (**a**) We model the operations (_e.g._, 1\(\times\)1-Conv) as edges; we model the outputs of such operations (_i.e._, featuremaps) as nodes (_e.g._, \(r,v_{2}\)); here \(r\) and \(d\) are the input and output nodes of the supernet \(G\), respectively. By removing some edges from supernet \(G\), we generate multiple subnetworks \(\{G_{k},\ k=1,...,T\}\). (**b**) We then build the adjacency matrices \(\{\mathbf{A}_{k},\ k=1,...,T\}\) for each subnetwork. We combine these adjacency matrices and the inter-subnetwork coupling matrices \(\{\widetilde{\mathbf{Z}_{i,j}},\ i\neq j\}\) to form the hyper-adjacency matrix \(\tilde{\mathbf{H}}(\lambda)\). (**c**) By solving Eq. (6)(7)(8), we get the TAS value of each node. After finding the path with the highest TPS value by Eq. 9 (Path2), we characterize the important operations (_i.e._, edges) of the AnytimeNN. We provide more examples in Appendix C.
At each training step, we sample \(T\) subnetworks as shown in Fig. 2(a). Let \(\mathcal{L}\) denote the loss function (_e.g._, cross-entropy). Then, the loss for AnytimeNNs at each training step is calculated by passing the same batch of images through these \(T\) subnetworks (Huang et al., 2018; Hu et al., 2019):

\[Loss=\sum_{k=1}^{T}\mathcal{L}(y,G_{k}(x)) \tag{3}\]

where \(x\), \(y\), \(G_{k}(x)\) are the input, ground truth, and output of subnetwork \(G_{k}\), respectively. Eq. 3 shows that all these subnetworks in Fig. 2(a) share the same input data and use the accumulated loss from all of them to calculate the gradient during the backward propagation. Hence, all these subnetworks are highly coupled with each other. Inspired by the idea in (Taylor et al., 2019), as shown in Fig. 2(b), we integrate multiple subnetworks into a new hyper-graph to capture the coupling impacts among different subnetworks. Specifically, given a sequence of \(T\) subnetworks and each subnetwork with \(N\) nodes, we construct a _hyper-adjacency matrix_\(\hat{\mathbf{H}}(\lambda)\in R^{NT\times NT}\):

\[\hat{\mathbf{H}}(\lambda)=\begin{bmatrix}\mathbf{A}_{1}&\widetilde{\mathbf{Z}_{1,2}}&... &\widetilde{\mathbf{Z}_{1,T}}\\ \widetilde{\mathbf{Z}_{2,1}}&\mathbf{A}_{2}&...&\widetilde{\mathbf{Z}_{2,T}}\\...&...&...&...\\ \widetilde{\mathbf{Z}_{T,1}}&...&...&\mathbf{A}_{T}\end{bmatrix} \tag{4}\]

where \(\widetilde{\mathbf{Z}_{i,j}}\in R^{N\times N}\) is the inter-subnetwork coupling matrix between _different_ subnetworks \(G_{i}\) and \(G_{j}\) as follows:

\[\widetilde{\mathbf{Z}_{i,j}}=\lambda\mathbf{I},\;i\neq j\;,\;0<\lambda\leq 1 \tag{5}\]

where \(\mathbf{I}\) is the identity matrix.

_Remark_: On the one hand, \(\mathbf{A}_{k}\) in \(\hat{\mathbf{H}}(\lambda)\) capture the connectivity pattern of each individual subnetwork. On the other hand, as shown in Fig. 2(a)(b), \(\widetilde{\mathbf{Z}_{i,j}}\) in \(\hat{\mathbf{H}}(\lambda)\) captures the inter-subnetwork coupling effects between every pair of subnetworks by connecting same nodes across different subnetworks1. Hence, our methodology does capture both _intra_- and _inter-subnetwork_ topological properties. This is crucial since AnytimeNNs have a variable network architecture. (see more discussion in Section 4.5 and Appendix B.4).

Footnote 1: The parameter \(\lambda\) controls the strength of the interactions between different subnetworks; see details in Sec 4.5.

#### 3.1.2 Building the DTMC for AnytimeNNs

In this work, we aim to identify the importance of each operation in AnytimeNNs. Inspired by the PageRank algorithm (Berkhin, 2005), we use the _hyper-adjacency matrix_\(\hat{\mathbf{H}}(\lambda)\) to build the transition matrix \(\hat{\mathbf{P}}\) of our DTMC. Specifically, we normalize the adjacency matrix \(\hat{\mathbf{H}}\) row by row:

\[\mathbf{P}_{m,:}=\hat{\mathbf{H}}_{m,:}(\lambda)/(\sum\nolimits_{n}\hat{\mathbf{H}}_{m,n }(\lambda)) \tag{6}\]

and obtain an irreducible, aperiodic, and homogeneous DTMC, which has a unique stationary state distribution (\(\mathbf{\pi}\)) (Hajek, 2015)2. The stationary distribution \(\mathbf{\pi}\) of such DTMC has the following property:

Footnote 2: More details are given in Appendix B.1

\[\mathbf{\pi}\mathbf{P}=\mathbf{\pi} \tag{7}\]

Hence, we can solve Eq. 7 to obtain \(\mathbf{\pi}\) for our DTMC. Next, we use \(\mathbf{\pi}\) to analyze the nodes in \(\hat{\mathbf{H}}(\lambda)\). We denote \(\mathbf{\pi}(s)\) as the stationary probability of a state \(s\). Note that, as shown in Fig. 2(a), a node \(r\) appears in all the \(T\) sampled subnetworks, hence it appears \(T\) times in \(\hat{\mathbf{H}}(\lambda)\); each node \(r\) from the supernet \(G\) corresponds to \(T\) nodes \(\{r_{k},\;k=1,...,T\}\) in the DTMC within \(T\) subnetworks \(\{G_{k},\;k=1,...,T\}\). For a given node \(r_{k}\) in the DTMC, we denote its stationary probability as \(\mathbf{\pi}(s_{r_{k}})\).

### Topological & Gradient Properties of AnytimeNNs

To analyze the importance of nodes and paths in AnytimeNNs, we propose the following definitions:

**Definition 1**.: **Topological Accumulated Score (TAS)** A _topological accumulated score_ of a node \(r\) from the supernet is its accumulated PageRank score across multiple subnetworks. For a given node \(r\) in \(V\), its TAS value \(\mu_{r}\) is:

\[\mu_{r}=\sum_{k=1}^{T}\mathbf{\pi}(s_{r_{k}}) \tag{8}\]

TAS quantifies the _accumulated probability_ that a node is selected within an AnytimeNN. Next, we use TAS to analyze the importance of various computation paths.

**Definition 2**.: **Topological Path Score (TPS)** In an AnytimeNN, we define a computation path \(l\) from a node \(r\) to a node \(d\), as a sequence of edges \(\{r\to v_{1}\rightarrow...\to v_{w}\to d\}\). The _topological path score_\(TPS_{l}\) of a computation path \(l\) is the sum of the TAS values of _all_ nodes traversed in the path:

\[TPS_{l}=\sum_{s\in\{r,v_{1},...,v_{w},d\}}\mu_{s} \tag{9}\]

The above definitions and the LDI discussion in Section 2 enable us to propose our main result:

**Proposition 3.1**.: _Consider an AnytimeNN initialized by a zero-mean i.i.d. distribution with variance \(q\). Given two computation paths \(l_{S}\) and \(l_{L}\) in this AnytimeNN with same width \(w_{r}\) and number of nodes \(D\), we define \(w_{c}^{S}\) (\(w_{c}^{L}\)) as the average degree of \(l_{S}\) (\(l_{L}\)). Assuming \(q\leq\epsilon\), \(w_{c}^{S}\gg w_{r}\), and \(w_{c}^{L}\gg w_{r}\), then the mean singular values \(E[\sigma^{S}]\) and \(E[\sigma^{L}]\) of the Jacobian matrix for \(l_{S}\) and \(l_{L}\) satisfy:_

\[\text{if }TPS_{l_{S}}\leq TPS_{l_{L}}\text{, then }E[\sigma^{S}]\leq E[\sigma^{L}]\leq 1 \tag{10}\]
_where, \(\epsilon=\frac{1}{max(w_{e}^{S},w_{e}^{L})+w_{e}+2\sqrt{max(w_{e}^{S},w_{e}^{L})w_{ r}}}\). That is, the mean singular value of the Jacobian for the computation path with higher TPS values is higher and closer to 1._

Proof.: Authors in (Bhardwaj et al., 2021) prove that for a given neural network initialized by a zero-mean i.i.d. distribution with variance \(q\), the mean singular value \(E[\sigma]\) of the Jacobian matrix from the network is bounded by the following inequality:

\[\sqrt{qw_{e}}-\sqrt{qw_{r}}\leq E[\sigma]\leq\sqrt{qw_{e}}+\sqrt{qw_{r}} \tag{11}\]

where the \(w_{e}\) is the _average node degree_ or _effective width_ and \(w_{r}\) is the real width of the neural network. In Fig. 3, we give an example of how \(w_{e}\) and \(w_{r}\) are calculated in a neural network.

We now use the above bounds to prove our main result. Let us first prove the right side of the inequality in Proposition 3.1. According to Eq. 11, for two computational paths \(l_{S}\) and \(l_{L}\), the mean singular values \(E[\sigma^{S}]\) and \(E[\sigma^{L}]\) of their Jacobian matrices are bounded by the following inequalities:

\[\sqrt{qw_{e}^{S}}-\sqrt{qw_{r}} \leq E[\sigma^{S}]\leq\sqrt{qw_{e}^{S}}+\sqrt{qw_{r}} \tag{12}\] \[\sqrt{qw_{e}^{L}}-\sqrt{qw_{r}} \leq E[\sigma^{L}]\leq\sqrt{qw_{e}^{L}}+\sqrt{qw_{r}}\]

Based on Eq. 12, we note that if initialization variance \(q\) satisfies

\[q\leq\frac{1}{max(w_{e}^{L},w_{e}^{S})+w_{r}+2\sqrt{max(w_{e}^{L},w_{e}^{S})w_{ r}}} \tag{13}\]

then, the mean singular value is always bounded by 1 for both \(l_{S}\) and \(l_{L}\); that is:

\[E[\sigma^{S}]\leq 1\ \ \ \ \ E[\sigma^{L}]\leq 1 \tag{14}\]

Inequality 14 proves the right side of inequality in Proposition 3.1. Next, we prove the left side.

Using Eq. 12, if \(w_{e}^{S}\gg w_{r}\) and \(w_{e}^{L}\gg w_{r}\), then the mean singular values of \(l_{L}\) and \(l_{S}\) are mainly determined by \(w_{e}^{L}\) and \(w_{e}^{S}\); that is:

\[E[\sigma^{L}]=\sqrt{qw_{e}^{L}}\ \ \ \ E[\sigma^{S}]=\sqrt{qw_{e}^{S}} \tag{15}\]

From Definition 1, we know that TAS of a given node is the sum of its PageRank across the \(T\) subnetworks. As discussed in (Fortunato et al., 2006), under the mean-field approximation, the PageRank of a given node is linearly correlated to its node degree. That is, for the \(i^{th}\) node \(i\) on the computation path:

\[\mu_{i}=\frac{k_{i}}{C} \tag{16}\]

where \(k_{i}\) is the node degree for node \(i\), and \(C\) is a constant determined by the topology of supernet3. Because both \(l_{S}\) and \(l_{L}\) are sampled from the same supernet, then they share the same value of \(C\). Combining Eq. 16 with Definition 2, the TPS satisfies the following relation:

Footnote 3: A supernet is the given neural architecture that needs to be converted into its AnytimeNN version.

\[TPS=\sum_{i=1}^{D}\mu_{i}=\frac{\sum_{i=1}^{D}k_{i}}{C} \tag{17}\]

Given the definition of average degree \(w_{e}\), we rewrite Eq. 17 as follows:

\[TPS=\frac{D\times w_{e}}{C}\Longrightarrow w_{e}=\frac{C\times TPS}{D} \tag{18}\]

where \(D\) is the number of nodes for a given path. By combining Eq. 15 and Eq. 18, the mean singular value is determined by \(q\), \(C\), \(D\), and \(TPS\):

\[w_{e}=\frac{C\times TPS}{D}\Longrightarrow E[\sigma]=\sqrt{\frac{q\times C \times TPS}{D}} \tag{19}\]

Note that \(q\), \(C\), \(D\) have the same values for both \(f_{S}\) and \(f_{L}\). Hence, if \(TPSS\leq TPSL\), then \(E[\sigma^{S}]\leq E[\sigma^{L}]\). This proves the left side of inequality in Proposition 3.1.

Therefore, the inequality in Proposition 3.1 holds true for both the left and right sides. That is, the mean singular value of the Jacobian for a computation path with a higher TPS is higher and closer to 1. Moreover, the closeness of \(E[\sigma]\) to 1 is determined by the initialization variance \(q\), constant \(C\), the values of \(TPS_{S}\) and \(TPS_{L}\), and #nodes \(D\). This completes our proof of Proposition 3.1. 

Intuitively, Proposition 3.1 says that the computation paths with high TPS values satisfy the LDI property and the gradient magnitude through such paths would not vanish or

Figure 3: A 2-layer MLP has three neurons per layer; the right version includes skip connections (purple) across layers, while the left does not. Both MLPs have a real width \(w_{r}\) of 3. The average degree \(w_{e}\) is calculated as the total links (weights and skip connections) divided by total neurons (excluding input neurons). The upper MLP in **(a)** has a \(w_{e}\) of \(18/6=3\), and the lower in **(b)** has a \(w_{e}\) of \(21/6=3.5\) due to skip connections.
explode, thus, having a higher impact on AnytimeNNs training. We provide empirical results to verify this in the experiments section.

```
Input: Supernet \(G\), search steps \(m\) Output: Pareto-optimal subnetworks set \(G_{P}\) Search: Initialize \(G_{P}=\phi\) for\(i=1\)to\(m\)do  Sample subnetwork \(G_{i}\) from \(G\)  Evaluate \(G_{i}\) and get its accuracy \(\Theta_{G_{i}}\) \(optimal=TRUE\)  Initialize false-Pareto Set \(G_{P_{out}}=\phi\) for\(G_{j}\) in \(G_{P}\)do if\(FLOPs_{G_{j}}\leq FLOPs_{G_{i}}\)and\(\Theta_{G_{j}}>\Theta_{G_{i}}\)then \(optimal=FALSE\) elseif\(FLOPs_{G_{j}}\leq FLOPs_{G_{i}}\)and\(\Theta_{G_{j}}<\Theta_{G_{i}}\)then  Add \(G_{j}\) to \(G_{P_{out}}\) endif endfor if\(optimal\)then  Add \(G_{i}\) to \(G_{P}\) endif  Remove false Pareto-optimal \(G_{P}=G_{P}\setminus G_{P_{out}}\) endfor
```

**Algorithm 1** Pareto-optimal subnetwork search

### Topologically Important Path Sampling (TIPS)

Among the computation paths with the same number of nodes of an AnytimeNN, we define the operations (_i.e._, edges) along the path with the highest TPS value as _important operations_; the rest of operations are deemed as _unimportant operations_ (see Path2 in Fig. 2(c)). According to Proposition 3.1, the path with higher TPS values has higher singular values of the Jacobian matrix. Hence, these important operations have a significant impact on the training process. Note that, previous works treat all operations uniformly (Chin et al., 2021; Wang et al., 2018). Instead, in our approach, we modify the sampling process during the training process and use a higher sampling probability to sample these important operations. We call this sampling strategy _Topologically Important Path Sampling (TIPS)_. More details are given in the experiments section.

### Pareto-Optimal Subnetwork Search

After the TIPS-based training, we use the Algorithm 1 to search for the Pareto-optimal subnetworks under various hardware constraints. To this end, we consider the number of floating-point operations (FLOPs) as a proxy for hardware resource constraints4. At runtime, one can select the proper subnetworks to quickly adapt to various hardware constraints; _e.g._, if the amount of currently available memory for a device drops below a threshold, we switch to a smaller subnetwork to meet the new memory budget.

Footnote 4: In practice, this can be easily replaced by some other hardware resource, such as memory or power consumption.

### Summary of Our Approach

In brief, our method consists of the following steps:

* **Step 1: TPS analysis** (Fig. 2) We sample subnetworks and exploit TPS (our DTMC-based metric for AnytimeNNs) to identify important operations.
* **Step 2: AnytimeNN training** We use TIPS by assigning a higher sampling probability to the important operations (as given by TPS) to _train_ AnytimeNNs.
* **Step 3: Pareto-optimal search** Before model deployment, we do an _offline_ search under _various_ hardware constraints. We store the full supernet and #channel configurations of the obtained subnetworks.

_Remarks_: Our framework involves two steps where we perform sampling. In Step 1, we conduct the TAS and TPS analysis without knowing the importance of each operation. Hence, to build the DTMC with the sampled subnetworks (Section 3.1), we uniformly sample these operations and ensure each operation is selected at least once during this stage. Once we compute the TAS and TPS values, we can identify the important and unimportant operations in a given supernet (Sections 3.2 and 3.3). During Step 2 (i.e., AnytimeNN training), operations are not sampled uniformly. Instead, important operations are sampled with a higher probability compared to unimportant operations. We provide more details in Section 4.3.

After Steps 1-3, _at runtime_, we use the best subnetwork configurations under various budgets. We provide the storage overhead and time efficiency analysis in Appendix B.8.

In terms of **time cost**: Step 1 takes only 39 seconds on a Xeon CPU for MobileNet-v2. Step 2 takes 97 hours on an 8-GPU server for 150 epochs, and Step 3 takes 8 minutes on an RTX3090 GPU. We note that Step 1 only has negligible time costs compared to AnytimeNN training. Moreover, Steps 1-3 are conducted offline and, hence, they result in zero overhead for the online inference.

## 4 Experimental Results

### Experimental Setup

In this section, we present the following experiments: (_i_) Verification of Proposition 3.1, (_ii_) Validation of TIPS, and (_iii_) Model complexity vs. accuracy results.

For the experiments (_i_) on Proposition 3.1, we build several MLP-based supernets on MNIST dataset by stacking several linear layers with 80 neurons (and adding residual connections between each two consecutive layers), then verify our Proposition 3.1 on these supernets.

For the experiments (_ii_) on TIPS, we use TPS and TAS to identify the importance of various operations in several networks (MobileNet-v2, ResNet, WideResNet, ResNext, and
EfficientNet) for the ImageNet dataset. We also present the comparisons between the training convergence for our proposed TIPS strategy and the previous SOTA methods (Chin et al., 2021; Yu and Huang, 2019) with the exact same setup (_i.e._, same data augmentation, optimizer, and learning rate schedule). More training details are given in Appendix B.2.

Finally, for experiments (_iii_), we take the MobileNet-v2 and ResNet34 trained with TIPS as supernets, and then search for Pareto-optimal subnetworks. We compare the accuracy-FLOPs tradeoffs of the obtained subnetworks with various training strategies.

### Verification of Proposition 3.1

To empirically validate Proposition 3.1, we consider several supernets with 80, 100, 120, and 140 layers (along with residual connections). We then randomly sample 8 subnetworks from these supernets and use Eq. 2, Eq. 4, and Eq. 6 to build the DTMC. After solving Eq. 7, we calculate the TAS for each node (_i.e._, output of various operations). Next, we set the path length to 50 as an example, then randomly sample multiple computation paths with 50 nodes from these supernets and calculate the corresponding {TPS, mean singular value} pairs. As shown in Fig. 5(a), for a supernet with specific depth (_e.g._, 80 layers), higher TPS values always lead to higher mean singular values (closer to 1). These results empirically validate our Proposition 3.1.

### Validation of TIPS

In order to verify the effectiveness of our topological analysis, we first explore the relationship between the _important operations_ and the test accuracy for various networks. To this end, before training, we first use our DTMC based framework to obtain the TAS for each node (Eq. 8). Next, among all the computation paths from input to output in the supernet, we find the path that has the highest TPS value (Eq. 9); we mark all operations along this path as important operations. Then, we prune the output channels of each operation _individually_ (with pruning ratios ranging from 1% to 99%), without pruning the channels of any other operation in the network. Meanwhile, we measure the test accuracy of the network after each pruning step. This way, we can analyze the impact of each operation on the test accuracy of a given network. Note that, we prune the last channels first. For example, to prune a convolution layer with 64 (0-63) channels with a pruning ratio of 75%, we directly set the output of the last 75% (16-63) channels to zero. As shown in Fig. 4, for various pruning ratios, pruning the important operations has a much higher accuracy drop than the unimportant ones. These experimental results show that the important operations found by our framework have a significant impact on the test accuracy of AnytimeNNs. Therefore, the proposed TAS and TPS metrics clearly identify the important operations and computation paths in AnytimeNNs.

Next, we evaluate the impact of TIPS on _training convergence_ of the AnytimeNNs. For this experiment, we train MobileNet-v2 with width-multiplier 1.4 on ImageNet dataset with (_i_) SOTA training strategies: Joslim, US-Nets, and DS-Net (Chin et al., 2021; Yu and Huang, 2019; Li et al., 2021), and (_ii_) our proposed TIPS. As explained in Section 3.2, a higher sampling probability for important operations helps more with the training process. However, if the sampling probability for important operations is too high, it hurts the diversity of sampled subnetworks. In the extreme case, we always end up sampling and training only the important operations, while the unimportant ones never get sampled and trained; this can hurt the test accuracy of AnytimeNNs. Hence, for our proposed TIPS strategy, we use a 50% higher sampling probability for important operations compared to unimportant operations. For example, if 40% of the output channels of unimportant operations are sampled, then 60% of the output channels of important operations are sampled (since 40%\(\times\)(1+0.5)=60%).

We note that previous methods (_e.g._, Joslim and US-Nets) use a uniform sampling for every subnetwork, _i.e._, the same sampling probability for all operations during the training process. In contrast, TIPS focuses more on important operations thus improving the LDI properties. As shown in

Figure 4: Pruning ratio of important and unimportant operations (as identified by TAS/TPS) vs. mean test accuracy on ImageNet (std. dev. shown with shade) on EfficientNet-B0, ResNet18 and MobileNet-v2. More results are given in Fig. 8 in Appendix A.
Fig. 5(b,c), by changing the sampling strategy, our TIPS based-training achieves a much faster training convergence for the supernet compared to Joslim and US-Nets. Hence, this validates that TIPS results in better trainability of the supernet.

### Pareto-Optimal AnytimeNN Search

We use the Algorithm 1 to search for Pareto-optimal subnetworks under various hardware constraints for MobileNet-v2 and ResNet34. After the search, we evaluate the obtained Pareto-optimal subnetworks and get their real test accuracy.

Table 1 demonstrates that our proposed TIPS achieves significantly higher accuracy than SOTA given similar FLOPs for ImageNet on MobileNet-v2. For example, assuming the hardware constraint is 500M FLOPs, TIPS has a 1.4%-2% higher accuracy on ImageNet than the SOTA; on Tiny-ImageNet with an 80M FLOPs budget, TIPS has 6.1%-6.6% higher accuracy than SOTA.

Moreover, as shown in Table 2, given the ResNet34 supernet with a 3.6G FLOPs budget on ImageNet, TIPS achieves 1.4%, 1.5%, and 1.9% higher test accuracy than Joslim, US-Nets and DS-Net, respectively (Chin et al., 2021; Yu and Huang, 2019; Li et al., 2021). On CIFAR100 dataset with a 120M FLOPs budget, TIPS has 1.5%, 2.9%, and 4.2% higher accuracy Joslim, US-Nets and DS-Net, respectively.

\begin{table}
\begin{tabular}{|c|c|c|c|c|c|c|} \hline \multicolumn{6}{|c|}{**CIFAR100**} \\ \hline FLOPS & 20M & 30M & 35M & 40M & 45M & 50M \\ \hline US-Nets & 61.5 & 62.9 & 64.8 & 65.5 & 65.6 & 66.5 \\ \hline Joslim & 62.0 & 62.7 & 63.1 & 63.7 & 64.1 & 65.0 \\ \hline DS-Net & 61.8 & 63.8 & 64.8 & 65.3 & 65.5 & 66.7 \\ \hline
**TIPS (Ours)** & **66.4** & **66.9** & **67.0** & **67.6** & **67.7** & **68.2** \\ \hline \hline \multicolumn{6}{|c|}{**Tiny-ImageNet**} \\ \hline FLOPS & 80M & 120M & 140M & 160M & 180M & 200M \\ \hline US-Nets & 47.0 & 47.3 & 48.3 & 49.0 & 50.2 & 51.4 \\ \hline Joslim & 47.4 & 47.9 & 48.7 & 49.5 & 50.3 & 50.7 \\ \hline DS-Net & 46.9 & 47.4 & 48.1 & 48.7 & 50.3 & 50.8 \\ \hline
**TIPS (Ours)** & **53.5** & **53.8** & **54.0** & **54.4** & **54.9** & **55.1** \\ \hline \hline \multicolumn{6}{|c|}{**ImageNet**} \\ \hline FLOPS & 260M & 320M & 400M & 450M & 500M & 600M \\ \hline US-Nets & 70.6 & 71.6 & 71.8 & 72.1 & 72.3 & 72.9 \\ \hline Joslim & 70.8 & 71.9 & 72.5 & 72.7 & 72.9 & 73.4 \\ \hline DS-Net & 70.6 & 72.1 & 72.5 & 72.6 & 73.0 & 73.3 \\ \hline
**TIPS (Ours)** & **71.8** & **73.2** & **73.6** & **74.0** & **74.3** & **74.7** \\ \hline \end{tabular}
\end{table}
Table 1: Comparison of Top-1 test accuracy vs. FLOPS (Million [M]) with SOTA training methods on MobileNet-v2. The best results are shown with bold fonts. The results are averaged over three runs. The std. dev. values are given in Table 4 in Appendix B.3.

\begin{table}
\begin{tabular}{|c|c|c|c|c|c|c|} \hline \multicolumn{6}{|c|}{**CIFAR100**} \\ \hline FLOPS & 120M & 180M & 200M & 220M & 240M & 260M \\ \hline US-Nets & 63.1 & 63.9 & 64.4 & 64.8 & 65.0 & 65.4 \\ \hline Joslim & 65.8 & 66.2 & 66.7 & 67.0 & 67.3 & 67.4 \\ \hline DS-Net & 64.4 & 65.9 & 66.2 & 66.4 & 66.5 & 66.6 \\ \hline
**TIPS (Ours)** & **67.3** & **67.4** & **67.8** & **67.9** & **68.1** & **68.2** \\ \hline \hline \multicolumn{6}{|c|}{**Tiny-ImageNet**} \\ \hline FLOPS & 130M & 190M & 220M & 250M & 270M & 300M \\ \hline US-Nets & 42.9 & 43.2 & 44.3 & 44.7 & 44.9 & 45.2 \\ \hline Joslim & 44.9 & **45.0** & 45.3 & 45.4 & 45.5 & 45.8 \\ \hline DS-Net & 41.8 & 43.0 & 43.8 & 43.9 & 44.1 & 44.2 \\ \hline
**TIPS (Ours)** & **44.1** & 44.6 & **45.4** & **45.8** & **45.9** & **46.0** \\ \hline \hline \multicolumn{6}{|c|}{**ImageNet**} \\ \hline FLOPS & 1.5G & 2.26 & 2.8G & 3.0G & 3.2G & 3.6G \\ \hline US-Nets & 67.8 & 69.2 & 69.7 & 70.1 & 70.2 & 70.5 \\ \hline Joslim & 68.0 & **69.4** & 69.6 & 70.0 & 70.2 & 70.4 \\ \hline DS-Net & 66.0 & 67.0 & 68.8 & 69.4 & 69.9 & 70.0 \\ \hline
**TIPS (Ours)** & **68.4** & 69.3 & **70.8** & **71.1** & **71.4** & **71.9** \\ \hline \end{tabular}
\end{table}
Table 2: Comparison of Top-1 test accuracy vs. FLOPS (Million/Giga [M/G]) with SOTA training methods on ResNet34. The best results are shown with bold fonts. The results are averaged over three runs. The std. dev. values are shown in Table 5 in Appendix B.3.

Figure 5: **(a)** Mean singular values (\(E[\sigma]\)) vs. TPS for various supernets (MLPs with various #layers) on MNIST. Clearly, paths with higher TPS values have higher \(E[\sigma]\) for a specific supernet (_e.g._, 80-layers). **(b, c)** Training loss of MobileNet-v2 (MBN-v2) based supernet vs. #Epochs on ImageNet and Tiny-ImageNet. TIPS requires much fewer epochs to achieve a target training loss. For example, on ImageNet, to make the training loss less than 1.25 on ImageNet, US-Nets takes 145 epochs while TIPS only needs 88 epochs.
**Latency vs. Accuracy Trade-off** Besides FLOPs vs. accuracy, we also compare the latency vs. accuracy tradeoff of subnetworks obtained by TIPS and Joslim. As shown in Table 3, TIPS achieves higher accuracy than Joslim, given a similar latency. For example, assuming the latency constraint is around 300ms, TIPS has a 1.1% higher accuracy on ImageNet than the Joslim.

### Ablation Studies

**Stability of TPS analysis** We vary the #sampled subnetworks from 2 to 20 for MobileNet-v2. As shown in Fig. 6, four subnetworks are typically enough to make the TPS value converge. In practice, we sample 8 subnetworks and the standard deviation of TPS values is less than 2.5% of the mean values.

**Effect of \(\lambda\)** Finally, we fix the #sampled subnetworks to 8 and vary the \(\lambda\) value in the hyper-adjacency matrix (Eq. 4) from 0.1 to 1 for MobileNet-v2. As shown in Fig. 7, the ranking among different paths remains the same under various \(\lambda\) values. Therefore, our approach is robust to \(\lambda\) values variation. In our approach, we set the value of \(\lambda\) to '1'. We discuss this in Appendix B.4.

### Limitations and Future Work

Our current framework (TIPS) has been primarily verified on CNNs with variable width and depth. We plan to explore it with other AnytimeNNs (_e.g._, multi-branch and early-exit networks) and other types of networks (_e.g._, transformers and graph neural networks). Also, in the current version, the hardware constraints are considered _after_ the supernet training; we intend to consider incorporating hardware awareness into the training process as well.

## 5 Conclusion

In this work, we have proposed a new methodology to _automatically design the AnytimeNNs_ under various hardware budgets. To this end, by modeling the training process of AnytimeNNs as a DTMC, we have proposed two metrics - TAS and TPS - to characterize the important operations in AnytimeNNs. We have shown that these important operations and computation paths significantly impact the accuracy of AnytimeNNs. Based on this, we have proposed a new training method called _TIPS_. Experimental results show that TIPS has a faster training convergence speed than SOTA training methods for anytime inference. Our experimental results demonstrate that our framework can achieve SOTA accuracy-FLOPs trade-offs, while achieving 2%-6.6% accuracy improvements on CIFAR100, Tiny-ImageNet and ImageNet datasets compared to existing approaches for anytime inference.

## Acknowledgement

This work was supported in part by the US National Science Foundation (NSF) grants CNS-2007284 and CCF-2107085.

\begin{table}
\begin{tabular}{|c|c||c|c|c|c|c|} \hline Method & Metric & \multicolumn{5}{c|}{Results} \\ \hline \hline \multirow{2}{*}{Joslim} & Latency (ms): & 176 & 232 & 305 & 341 & 406 \\ \cline{2-7}  & Accuracy (\%) & 70.8 & 71.9 & 72.5 & 72.9 & 73.4 \\ \hline \hline \multirow{2}{*}{**TIPS (Ours)**} & Latency (ms): & 190 & 245 & 298 & 362 & 413 \\ \cline{2-7}  & Accuracy (\%) & 71.8 & 73.2 & 73.6 & 74.3 & 74.7 \\ \hline \end{tabular}
\end{table}
Table 3: Top-1 test accuracy vs. latency of MobileNet-v2 on ImageNet for RaspberryPi-3B+. The results are averaged over three runs.

Figure 6: Stability of TPS values vs. #subnetworks over 10 runs (std. dev. shown with shade) for MobileNet-v2. The variation is negligible when #subnetworks is larger than 4.

Figure 7: TPS values vs. \(\lambda\) values for MobileNet-v2. The ranking among different paths remains the same for various \(\lambda\) values.