Alvin Wan
Hanxiang Hao
Kaushik Patnaik
Yueyang Xu
Omer Hadad
David Güera
Zhile Ren
Qi Shanapple

appleApple, Cupertino, USA

Alvin<EMAIL_ADDRESS>Qi<EMAIL_ADDRESS>
Machine Learning, ICML

As neural networks grow in size and complexity, inference speeds decline. To combat this, one of the most effective compression techniques – channel pruning – removes channels from weights. However, for multi-branch segments of a model, channel removal can introduce inference-time memory copies. In turn, these copies increase inference latency – so much so that the pruned model can be slower than the unpruned model. As a workaround, pruners conventionally constrain certain channels to be pruned together. This fully eliminates memory copies but, as we show, significantly impairs accuracy. We now have a dilemma: Remove constraints but increase latency, or add constraints and impair accuracy. In response, our insight is to reorder channels at export time, (1) reducing latency by reducing memory copies and (2) improving accuracy by removing constraints. Using this insight, we design a generic algorithm [<https://github.com/apple/ml-upscale>] to prune models with any pruning pattern. By removing constraints from existing pruners, we improve ImageNet accuracy for post-training pruned models by 2.1 points on average – benefiting DenseNet (+16.9), EfficientNetV2 (+7.9), and ResNet (+6.2). Furthermore, by reordering channels,  improves inference speeds by up to 2$\times$ over a baseline export.

Our export achieves lower latency (, solid) than the baseline export (dotted) for an unconstrained pruned model. Notice the baseline export (dotted) is unable to achieve a latency lower than the unpruned model's latency of $\sim$1.1ms, even with over 95% sparsity levels. By contrast, our export (solid) reduces latency more appropriately. The above plot features MobileNetV3-Small pruned at various sparsity levels, using existing pruning heuristics (FPGM, HRank, LAMP) but modified to run without channel constraints.

Unconstrained pruning patterns are non-trivial to export. Left: Different convolutions (II, III) prune different channels in a shared tensor $X$. As a result, channels from $X$ are copied during inference time to assemble inputs for II (purple), III (blue). Unfortunately, these memory copies incur significant latency costs. Middle: To sidestep this, previous methods constrain all convolutions (II, III) to prune the same channels. Since all convolutions prune the same channels, the common, pruned filters can be removed before inference, converting convolution I into I'. However, these constraints limit the pruned model's accuracy. Right: To eliminate memory copies without constraints, we reorder output channels in convolution I to generate I'. This way, inputs for downstream convolutions (II, III) are contiguous in memory, in $Y$. Our  algorithm computes this reordering.

Removing pruning constraints improves accuracy. Above is the accuracy of unconstrained minus constrained pruned models, averaged across sparsity levels and heuristics. Positive values mean that unconstrained pruning outperforms constrained pruning. For example, on DenseNet121, unconstrained outperforms constrained pruning by an average of 16.9 points. This is generally true as the model grows larger; we hypothesize this is due to larger models with more channels having more constraints. For example, ResNet18 (-0.8) favors constrained pruning, but its larger variants ResNet50 (+3.1) and ResNet101 (+6.2) both favor unconstrained pruning. The same pattern repeats for MobileNetV3.

§ INTRODUCTION

Deep neural networks are intrinsic to an increasing number of real-world applications, but neural network architectures are simultaneously growing in size and complexity, year over year. This is problematic for a growing number of uses cases with inference-time resource constraints, making model compression techniques a necessity.

One of the most effective families of model compression methods is channel pruning, which removes entire channels of convolutional or dense weights to reduce inference-time latency. Despite its effectiveness, the process of channel removal itself – which we refer to as the export step – is non-trivial and is often overlooked. This leads to two disagreeable options for channel pruning: (1) Add constraints, per convention, that impede accuracy, or (2) remove constraints and unsustainably increase inference-time latency.

First, without constraints, exporting is non-trivial specifically for multi-branch segments of network. In these segments, layers from different branches may all use the same input feature map and simultaneously prune different channels. This causes incompatible dimensions and more importantly, during inference time, the network must then perform memory copies to ensure that tensors are contiguous in memory. These memory copies are latency hungry – so much so that pruned models can be even slower than unpruned models (Figure <ref>).

Second, to address this, early works established convention by adding constraints [Li et al., 2017, Wen et al., 2016] – specifically, constrain layers in all branches of a segment to prune the same channels. These constraints simplify export, and as a result, modern pruning works focus on which channels to prune rather than how to remove them during export. Yet, despite significant progress in structured pruning, these constraints impair accuracy [Liu et al., 2019]. Intuitively, constraints restrict the set of possible pruning patterns, limiting pruning's effectiveness (Figure <ref>).

To tackle this problem, our insight is two-fold: (1) reordering channels can keep subsets of the tensor contiguous and (2) contiguous slices of a tensor are “free” to use, without memory copies. In short, this allows us to abandon conventional pruning constraints to obtain higher accuracy. Furthermore, by eliminating memory copies, this allows accuracy gains to come at a reduced latency penalty.

These insights yield a general-purpose export algorithm  () that can prune models with any pruning pattern. This enables a broader class of possible pruning algorithms by making latency for unconstrained pruned models much more palatable – in some cases, almost fully eliminating extraneous memory copies. This work yields the following three contributions:

* Comparison of unconstrained and constrained pruning accuracy, on a variety of pruning heuristics, architectures, and sparsity levels. Unconstrained pruning improves post-training pruned accuracy by an average of 2.1 points on ImageNet.

* A generic export utility for unconstrained pruning dubbed , which produces models with inference times over $2\times$ faster than baseline export. This drop-in utility enables future researchers to abstract away export concerns. To the best of our knowledge, we are the first to develop an export utility that can support unconstrained pruning patterns.

* Graph formulation of memory copy maximization, an abstraction that may open opportunities for further latency optimizations.

Pipeline to export a model pruned without constraints: Top: Consider a typical residual block on the left. Underneath, we list the in and out channels, as well as the kernel size. In Step 1, extract a segment: This includes the $A \rightarrow B, A \rightarrow D, C \rightarrow D$ edges. Convolution B retains channels 1, 3; D retains 2, 4. Notice B and D retain disjoint sets of channels. Redraw in “canonical” form, with producers on the left and consumers on the right. This helps visualize constraints. In Step 2, construct a graph. Since B and D don't retain any shared channels, they don't share an edge. There are now two paths, each just a single node (dotted circles). In Step 3, order the channels. Simply place the channels for each path one after another. In Step 4, use this channel ordering to reorder channels for all convolutions. Bottom: In Step 1, extract a segment. This time, D retains 2,3. Notice B and D share a retained channel (3). In Step 2, draw two nodes for the two consumers B and C. Since B and D both retain 3, they share an edge. Find a maximum reward acyclic path, which includes the only two nodes (gray, dotted line). In Step 3, list channels unique to B (1), those shared by B and D (3), then those unique to D (2). In Step 4, reorder channels.

§ RELATED WORK

Structured vs. Unstructured Pruning. Existing pruning work can be divided into unstructured methods [Han et al., 2016, Molchanov et al., 2017, Janowsky, 1989, Frantar & Alistarh, 2022, Yu et al., 2022, He et al., 2022] and structured methods [Anwar et al., 2017, He et al., 2017, Sze et al., 2017, Molchanov et al., 2017, Zhu & Gupta, 2017, Huang & Lee, 2021]. Unstructured methods threshold and zero individual weight values, whereas structured methods impose structure on sparsity patterns at various levels of granularity – from pruning in blocks [Narang et al., 2017] to removing entire channels [Lee et al., 2021, Lin et al., 2020] – the latter of which is called channel pruning [Wen et al., 2016]. Channel pruning is a unique pruning strategy, as its benefits are not dependent on custom sparse matrix primitives [Buluç & Gilbert, 2012, Azad & Buluç, 2017, Baskaran & Bordawekar, 2009, Vuduc et al., 2005]. Instead, channel pruning's benefits stem from removing convolutional weight channels at export time, reducing resource consumption at inference time.

Channel Pruning Strategies In addition to its unique benefit, channel pruning introduces a unique challenge: removing channels is difficult for complex topologies, especially when multiple branches in a network use or produce a shared tensor. In response, prior work [He et al., 2017, Wen et al., 2016, Li et al., 2017] imposes constraints on pruning masks, restricting the set of possible pruning patterns in complex portions of a network. Most work in structured pruning focuses on other aspects of pruning, other than exporting – including heuristics for importance, whether local to a segment of the network [Han et al., 2015] or global, across layers and channels [Lee et al., 2019, Frankle & Carbin, 2019]; the amount to sparsify at once [Liu et al., 2017, Gale et al., 2019]; and techniques for learning masks, whether using additional networks or layers [Huang et al., 2018, Yamamoto & Maeno, 2019, He et al., 2018] or auxiliary variables [Guo et al., 2016, Savarese et al., 2020, Courbariaux et al., 2015, Louizos et al., 2018, Srinivas et al., 2017, Xiao et al., 2019, Bengio et al., 2013].

Notably, these works overlook the export challenge for two reasons: Most works (1) apply zero-one masks during training to mimic pruning [He et al., 2019, He et al., 2017, Yu et al., 2022], without ultimately removing channels; this means the challenge of dropping channels from multi-branch segments is never surfaced. Most works furthermore (2) report FLOPs as a proxy for latency [He et al., 2019, Reed, 1993, Blalock et al., 2020, Li et al., 2022, Miao et al., 2021, Wang et al., 2022, Li et al., 2022, Shang et al., 2022]; this means that the latency impact of memory copies would have never been realized, had these works removed constraints. The combination of both practices thus hides export-related challenges. To remedy this, we study export directly to allow a broader class of pruning algorithms, showing that existing pruning heuristics can attain higher accuracy by simply removing these constraints.

[1]
$L \gets$ model.layers
left0top0 producers $\gets$ $\{L\textrm{.pop()}\} $Sec <ref>
consumers $\gets$ {}
$N \gets$ 0
Len(producers) + Len(consumers) $> N$
N $\gets$ Len(producers) + Len(consumers)
consumers $\gets$ Consumers(producers)
producers $\gets$ Producers(consumers)

left1top1 $c \gets$ model.channels
$G \gets$ consumers Sec <ref>

$n \in G$
$R_n[n] \gets \textsc{len}(c[n])$
$m, n \in G$
$R_e[m,n] \gets -\textsc{len}(c[m] \cap c[n])$
$A \gets R_e > 0$edge if $> 0$ shared channels
$\Pi_i \gets$ Reduce(producers)Sec <ref>

left2top2 o $\gets$ []
$G$Sec. <ref>
$p \gets \textsc{Mrap}(G)$Eqn. <ref>
$n_i$ in $p$Sec. <ref>
$\tilde{n_i} \gets n_i - n_{i-1} - n_{i+1}$Eqn. <ref>
o.extend($\tilde{n_i} \cup (n_i \cap n_{i+1})$) Eqn. <ref>
$G \gets G - p$

left3top3$W \gets$ model.weights
$\Pi \gets \pi(o)$to permutation matrix
$p_i$ in producers Sec <ref>
$W[p_i] \gets W[p_i] \Pi_i \Pi$
$c_i$ in consumers
$W[c_i] \gets W[c_i] \Pi$

top0bottom0left01. segment net
top1bottom1left12. define graph
top2bottom2left23. compute order
top3bottom3left34. reorder weights

§ METHOD

Previous work focuses on pruning strategies, which mimics pruning patterns by “zero'ing”, channels during training. Our work is orthogonal to this line of work, instead focusing on how to export unconstrained pruning patterns.

Both the input and output channels in a kernel can be pruned; pruning the former is called “input pruning” (, place the pruning mask before the convolution layer), and pruning the latter is called “output pruning” (, place the pruning mask after the convolution layer). Without loss of generality, we will focus on unconstrained input pruning. To see an explicit description of unconstrained output pruning, see Appendix <ref>.
We also empirically observe that input pruning generally outperforms output pruning (Figures A.<ref>, A.<ref>), motivating our focus on input pruning.

Note that throughout this methods section, we explicitly specify “convolutions” for ease of understanding. However, our algorithm generalizes to any operation where the number of input channels is independent from the number of output channels, such as dense layers.

§.§ Step 1 - Reduce to a Segment

Our algorithm divides the network architecture into segments (Figure <ref>, Step 1) – informally, a set of layers that can be pruned independently of the rest of the network. A segment includes (a) convolutions that produce outputs, dubbed producers and (b) convolutions that consume those tensors, dubbed consumers.

To identify segments, start from an arbitrary producer. Find all consumers for that producer, then find all producers for those consumers. Repeat iteratively until both sets converge. See Algorithm <ref> for a more exact formulation.

For example, in Figure <ref> (Step 1), start from producer $A$. Find $A$'s consumers: $\{B, D\}$. Find their producers: $\{A, C\}$. Find their consumers: $\{B, D\}$. Notice our set of consumers has converged, so our segment is complete. This segment can now be pruned independently of the rest of the network, reducing the problem of pruning a network to pruning a single segment. See Figure A.<ref> for more examples.

§.§ Why Memory Copies Occur

In a nutshell, memory copies occur when consumers prune different channels. To handle this, prior methods simply constrain all consumers to prune the same channels, as in Figure <ref>, “Constrained”. Since both consumers are constrained to prune the same channels, this is trivial to export: Simply drop the producer's output channels that all consumers prune.

However, consider now the unconstrained case in Figure <ref>, “Inefficient”. Say consumer II prunes channels that consumer III does not. At export time, we cannot drop channels that II prunes, since III still needs it. Instead, during inference time, we subselect the producer's output – copy every unpruned channel that II needs into a new tensor – to then pass to II. This method is the baseline approach to exporting unconstrained pruned models.
Unfortunately, the memory copies in the baseline approach incur significant latency costs at inference time, so much so that this pruned model incurs higher latency than the original, unpruned model (Figure <ref>).

Our key insight is that contiguous slices are “free”. In other words, each consumer takes a slice of the input tensor, instead of copying channels into a new tensor. We therefore design an algorithm that reorders producer output channels and consumer input channels (Figure <ref>, “Ours”, Sec <ref>). We now discuss how to compute this reordering.

Dividing a graph into maximum reward acyclic paths. This is a more detailed version of Fig <ref>, where we show a slightly more involved example. Left: We have a segment in canonical form, with 1 producer and 3 consumers. Center: We build the graph, with one node per consumer. Notice every consumer shares a channel with every other consumer. This means the graph is fully-connected, creating a cycle. B has a reward of 2 since B retains 2 channels. D and E both retain 3 channels so have a reward of 3. Every pair shares exactly 1 retained channel, so every edge has a reward of -1. Right: We find the maximum reward acyclic path. Since the graph is fully-connected, any pair of nodes is a viable path: BD, BE, or DE. Of the 3, DE has the highest reward (3 + 3 - 1), so DE is “Path 1”. B is then “Path 2”.

§.§ Step 2 - Formulate as a Graph

To simplify explanations, moving forward, we will refer to the channels that a consumer retains, rather than the channels that it prunes.

To formalize our objective, we formulate our constraints as an undirected graph (Figure <ref>, Step 2): Each node in our graph represents the set of channels that a consumer retains. Two nodes share an undirected edge if both nodes share one more more retained channels. Each node's reward is the number of retained channels, and each edge's reward is negative of the number of shared retained channels. We will discuss why shortly. With this graph, we can formalize our memory-copy maximization objective.

Our goal is to find a path – or in other words, a sequence of nodes: Since each node is a consumer, a sequence of nodes represents a sequence of consumers. In turn, every sequence of consumers admits a zero-copy order of channels. For example, say we have two consumers with node sequence $A, B$. The zero-copy channel order can be obtained by: ordering channels retained only by $A$, then channels shared by $A$ and $B$, then channels retained only by $B$. This ordering ensures zero memory copies, as both $A$ and $B$'s inputs are already contiguous in memory. We can continue indefinitely for any number of consumers, so long as the consumers are ordered in a sequence. In sum, a path can be translated into a zero-copy channel ordering. For more examples, see Appendix <ref>.

Our goal is to find an acyclic path: Say the first and last nodes in our path share channels. Now, there's a dilemma: Place the shared channels either at the beginning or the end of the channel ordering. Either way, at least one consumer will have its input spread non-contiguously in memory.  More generally, non-adjacent consumers in the sequence cannot share channels. In other words, no two non-adjacent nodes can share an edge – or more succinctly, the path must be acyclic; otherwise, we will need to introduce additional memory copies for the shared channels during inference.

Our goal is to find the maximum reward acyclic path: As mentioned earlier, all channels in a path require zero copies, so to minimize memory copies, maximize the number of channels included in the path. Previously, we defined node and edge reward so that path reward is equal to the number of channels included in a path. As a result, in turn, maximizing included channels maximizes path reward.

Our final, formal objective is to find the maximum reward acyclic path. For end-to-end examples of how this minimizes memory copies, see Appendix <ref> or Figure A.<ref>.

Unconstrained Outperforms Constrained Pruning Accuracy for larger models and models with complex topologies. The above models are pruned, then evaluated on ImageNet's validation set across various sparsity levels. Unconstrained pruning (solid) achieves higher accuracy than constrained pruning (dashed), with benefits varying depending on the pruning strategy. Per figures A.<ref>, A.<ref> input pruning outperforms output pruning in our experiments, so we narrow our focus to input pruning in the main text. Pruning heuristics include L1 [Li et al., 2017], L2 [Wen et al., 2016], LAMP [Lee et al., 2021], FPGM [He et al., 2019], and HRank [Lin et al., 2020]. Architectures include DenseNet [Huang et al., 2017], EfficientNetV2 [Tan & Le, 2021], ResNet [He et al., 2016]. See all 80+ plots across architectures and heuristics in figures A.<ref>, A.<ref>.

§.§ How to Find Maximum Reward Acyclic Path

We start by computing the reward of the maximum reward path, which we abbreviate as “mrp”. To compute this reward $\textsc{Mrp}(G)$ for a graph $G$, iterate over all nodes $s \in G$, and compute reward $f(s)$ of the mrp starting from node $s$.

\begin{equation}
\label{eqn:mrp}
\textsc{Mrp}(G) = \textsc{max}(\{f(s) : s \in G\})
\end{equation}

Our goal is now to define $f(s)$. To do so, consider all of node $s$'s neighbors: $n \in A[s]$, for adjacency matrix $A$. Intuitively, the reward $f(s)$ of the mrp is the maximum (a) reward of all maximum reward paths starting from its neighboring nodes $f(n) : n \in A[s]$, along with (b) the reward of traveling to its neighboring nodes $R_e[s, n]$, for edge reward matrix $R_e$. Recall that $R_e$ is the number of shared channels. This is summarized in the following recurrence relation

\begin{equation}
f(s) = \textsc{max}(\{f(n) + R_e[s, n]: n \in A[s]\}) + R_n[s]
\end{equation}

for node reward matrix $R_n$. Recall $R_n$ is the number of channels that a consumer retains. This finds the maximum reward path, but it does not handle the acyclic constraint. Note that the mrp path $p$ is the node sequence obtained by optimizing the objective (i.e., Eqn <ref>) via dynamic programming.

Handling the acyclic constraint: We abbreviate maximum reward acyclic path as “mrap”. To handle the acyclic constraint, we define a set of nodes $I$, which includes all invalid nodes. Invalid nodes include (a) already-traversed nodes included in the current path, as well as (b) nodes neighboring the path – , nodes sharing an edge with a node in the path. Our path is guaranteed to be acyclic if we never traverse nodes neighboring our path. We redefine our subproblem to be $f(s, I)$, the reward of the mrap starting from source node $s$ and excluding nodes in $I$.

We can then amend our original objective to be the following. The initial invalid set $I$ is the only node in the path, $\{s\}$.

\begin{equation}
\label{eqn:mrap}
\textsc{Mrap}(G) = \textsc{max}(\{f(s, \underbrace{\{s\}}_{I}) : s \in G\})
\end{equation}

We can then amend the recurrence relation to be the following. For convenience, we factor out the definition for $g(s, n, I)$, which is the reward of traveling only from $s$ to $n$ while avoiding invalid set $I$.

\begin{align}
\label{eqn:dp-invalids}
f(s, I) &= \textsc{max}(\{g(s, I, n): n \in \overbrace{A[s] - I}^{\textrm{ignoring }I}\}) + R_n[s] \notag \\
g(s, I, n) &= f(n, \underbrace{I \cup \{n\} \cup A[s]}_{\textrm{expanding }I}) + R_e[s, n]
\end{align}

Less formally, Eqn <ref> excludes all invalid nodes when considering neighbors to traverse to. When considering each neighboring node, we expand the invalid set $I$ by adding the neighboring node itself $\{n\}$, as well the source node's neighbors $A[s]$.

Necessity of Reordering for Latency Improvement: We observe that baseline unconstrained pruning export (dashed) can actually be detrimental to total latency, even increasing latency beyond that of the unpruned model. By contrast, using  (solid), the pruned model sees more appropriate latency reductions. To visualize the upper bound on 's latency savings, we include latency for a theoretical, zero-memory-copy export (dotted).  vastly outperforms the baseline export and for mobile models such as SqueezeNet (green), 's latency (solid green) even approaches the optimal latency reduction (dotted green). Architectures include MobileNetV3 [Howard et al., 2019], MnasNet [Tan et al., 2019], SqueezeNet [Iandola et al., 2016]. See all plots in Figure A.<ref>.

§.§ Step 3 - Compute Channel Order From Graph

Note that the maximum reward acyclic path $p$ can be obtained by solving the optimization (i.e., Eqn <ref>) via dynamic programming, which is denoted as $p \gets \textsc{Mrap}(G)$. Furthermore, the mrap path $p$ may not include all nodes – for example, if all nodes lie in a ring. As a result, continue to find paths on all remaining nodes $\textsc{Mrap}(G - p)$ until there are no more nodes remaining.

The paths we find in the previous step are then translated into a final channel ordering. As in Section <ref> and Figure <ref> (Case 2), say we have two consumers, $A, B$. Order channels retained only by $A$, then channels shared by $A$ and $B$, then channels retained only by $B$. For example, say $A$ retains 1, 3 and $B$ retains 2, 3. Order $A$-only channels (1), then shared channels (3), then $B$-only channels (2) to produce a final ordering: 1, 3, 2.

More generally, we denote the ordered nodes in the mrap path as $p = [n_1,n_2,n_3,\ldots]$. We first take all the channels that are retained only by the first node, which we denote $\tilde{n_1}$. The first node should only share channels with the second node, so this is equivalent to computing the set subtraction:

\begin{equation}
\tilde{n_1} = n_1 - n_2
\end{equation}

More generally, we denote channels “unique” to node $i$ as $\tilde{n_i}$. The ith node should only share channels with the previous $n_{i-1}$ and next $n_{i+1}$ nodes, so take the difference to find all channels “unique” to node $n_i$.

\begin{equation}
\label{eqn:channels-unique-to-node}
\tilde{n_i} = n_i - n_{i-1} - n_{i+1}
\end{equation}

Then, take all channels shared by the first and second nodes, $n_1 \cap n_2$. Then, take channels unique to the second node $\tilde{n_2}$. Then, take channels shared by the second and third nodes, $n_2 \cap n_3$. Continue this for all nodes in the path. The total ordering looks like the following

\begin{equation}
\label{eqn:channel-ordering}
\tilde{n_1} \cup (n_1 \cap n_2) \cup \tilde{n_2} \cup (n_2 \cap n_3) \cdots
\end{equation}

Once the path is exhausted, continue the ordering with nodes in the following path. Once all paths are exhausted, the ordering is complete. This channel ordering is summarized as a permutation matrix $\Pi$ in Algorithm <ref>. See Figure <ref> (Step 3) or Figure A.<ref> for examples.

§.§ Step 4 - Reorder Weights

The channel ordering from the previous step is then used to reorder channels in producers and consumers. First, the channel order directly determines output channel order for all producers in the segment. More formally, for a list of model weights $W$ and producer index $p_i$, we denote the channel reordering as $W[p_i] \Pi$. Second, for each consumer, reorder the consumer's input channels accordingly (, $W[c_i] \Pi$). See the full algorithm in Algorithm <ref>, description in Appendix <ref> or example in Figure <ref> (Step 4).

§.§ Generalized Method

Some nodes are subsets of other nodes. For example, consumer $A$ retains 1, 2, 3; consumer $B$ retains 1, 2; and consumer $C$ retains 2, 3. $A$ is the parent node and $B, C$ are the children nodes. Even though $A, B, C$ form a cycle in our graph, we can achieve a zero memory copy solution that accommodates all three consumers. Simply order channels as 1, 2, 3. This contradicts our acyclic path requirement. To handle this, we introduce two modifications: (1) Parent-child edges are ignored when rejecting cyclic paths, and (2) If child nodes in the path include all parent node channels, then the parent node's reward is added to the path's reward. For an extended description of this subset case and its resolution, see Appendix <ref>.

Multiple producers. Our algorithm above assumes there is only one producer. To handle multiple producers, we find which channels correspond to one another, across producers. Say producer $A$ and $B$'s outputs are simply summed. In this case, channel 1 from $A$ is equivalent to channel 1 from $B$. Channel 2 from $A$ is equivalent to channel 2 from $B$, and so on and so forth. Knowing this, we can reduce to the single producer case, as an ordering for $A$'s filters automatically provides the ordering for $B$'s filters.

We can then run our method assuming convolution $A$ is the only producer. Afterwards, when reordering the producer weights (, step 4), we map the original permutation $\Pi$ to each producer via the aforementioned equivalent channel map $\Pi_i$. Then order the weights by $W[p_i] \Pi_i \Pi$.
For a more detailed description and examples, see Appendix <ref>.

§ EXPERIMENTS

We present extensive experimentation to show that unconstrained pruning can attain significantly higher accuracy than constrained pruning, especially for modern, larger models and for those with complex topologies. For these unconstrained pruned models, we then show that  outperforms a baseline export in inference-time latency – in fact, without , latency of the pruned models actually increases, making  necessary for export. All prior methods utilize constrained pruning, so for our experiments, we remove those constraints and instead use  to export.

Model     Heuristic     Statistic     1%     5%     10%     15%     20%     25%     30%

Densenet121     HRank     Acc (Ours)     72.04%     63.59%     40.68%     17.95%     4.87%     1.59%     0.62%

Acc (Cons)     72.36%     54.10%     17.03%     11.95%     1.46%     0.47%     0.11%

Lat (Ours)     5.44 ± 0.018     5.67 ± 0.016     5.69 ± 0.010     5.49 ± 0.005     5.41 ± 0.008     5.29 ± 0.005     5.63 ± 0.0085

Lat (Base)     5.93 ± 0.007     6.13 ± 0.004     6.15 ± 0.017     5.94 ± 0.011     5.89 ± 0.013     5.76 ± 0.008     6.11 ± 0.008

Lat (Zero)     5.29 ± 0.012     5.25 ± 0.003     5.21 ± 0.008     4.98 ± 0.004     4.93 ± 0.005     4.79 ± 0.003     5.59 ± 0.004

Squeezenet1_1     L2     Acc (Ours)     57.71%     39.84%     9.44%     0.88%     0.35%     0.19%     0.13%

Acc (Cons)     57.71%     29.70%     5.80%     1.41%     0.32%     0.12%     0.14%

Lat (Ours)     0.67 ± 0.003     0.67 ± 0.001     0.67 ± 0.002     0.67 ± 0.002     0.66 ± 0.002     0.65 ± 0.003     0.65 ± 0.002

Lat (Base)     0.73 ± 0.003     0.81 ± 0.001     0.84 ± 0.002     0.85 ± 0.002     0.82 ± 0.001     0.82 ± 0.003     0.81 ± 0.003

Lat (Zero)     0.67 ± 0.002     0.68 ± 0.001     0.67 ± 0.003     0.67 ± 0.001     0.67 ± 0.004     0.66 ± 0.001     0.65 ± 0.001

Mobilenet_v3_large     L1     Acc (Ours)     73.72%     64.88%     39.87%     2.23%     0.49%     0.16%     0.21%

Acc (Cons)     73.69%     52.93%     22.81%     1.06%     0.14%     0.18%     0.15%

Lat (Ours)     1.80 ± 0.005     1.75 ± 0.004     1.78 ± 0.005     1.75 ± 0.001     1.71 ± 0.004     1.69 ± 0.001     1.58 ± 0.003

Lat (Base)     1.77 ± 0.004     1.88 ± 0.008     1.89 ± 0.005     1.86 ± 0.003     1.82 ± 0.004     1.84 ± 0.003     1.84 ± 0.003

Lat (Zero)     1.56 ± 0.001     1.55 ± 0.002     1.49 ± 0.006     1.47 ± 0.002     1.45 ± 0.002     1.48 ± 0.003     1.43 ± 0.003

Unconstrained vs. Constrained Accuracy and Latency after applying post-training pruning – experiments on various heuristics and architectures, across sparsity levels. Unconstrained accuracy matches or outperforms the baseline constrained accuracy. See full results across architectures, heuristics, and sparsity levels in Tables A.<ref>, A.<ref>, A.<ref>, A.<ref>.
Easter Egg #2!

Model     Type     1%     10%     20%     30%     40%

Ours     76.2%     74.4%     66.4%     46.0%     7.1%

Cons     75.9%     72.0%     58.8%     24.4%     0.7%

Ours     78.0%     76.8%     69.8%     53.0%     15.2%

Cons     77.7%     73.3%     60.1%     20.0%     0.4%

Ours     80.3%     78.7%     65.6%     3.8%     0.3%

Cons     80.0%     11.4%     0.1%     0.1%     0.1%

Unconstrained vs. Constrained ImageNet Accuracy after applying post-training pruning, across sparsity levels. Experiments above all use the LAMP heuristic. Unconstrained (Ours) accuracy outperforms baseline constrained (Cons) accuracy.

For the post-training setting, unconstrained pruning improves ImageNet top-1 accuracy by up to 76.7 points over constrained pruning. Our goal is to assess the accuracy impact of switching from constrained to unconstrained pruning. For simplicity, we naively adapt pruning algorithms previously used for constrained pruning, to the unconstrained setting, by removing constraints on the pruning zero-one masks. To evaluate the effect of constrained or unconstrained pruning, independent of training recipes, we conduct experiments without fine-tuning, dubbed post-training pruning: (1) Take models pretrained on ImageNet, (2) apply various pruning heuristics at different sparsity levels, and (3) measure ImageNet top-1 validation accuracy. We sparsify parameters at intervals of 2.5% from 0% to 100% and test 5 pruning strategies across 15+ architectures.

Although these pruning strategies were designed for constrained pruning, we find that unconstrained pruning achieves comparable or better accuracy than constrained pruning, for an average 2.1 point win averaged across all settings. For several cases, especially for complex topologies and larger models (Figure <ref>), unconstrained pruning yields significant accuracy benefits, up to a 21.7-point (DenseNet121, L1) increase in ImageNet accuracy, averaged across all sparsity levels – or, up to a 76.7-point increase at a specific sparsity level (EfficientNetV2-Small, LAMP, 12.5%). This demonstrates that unconstrained pruning can provide outsized benefits in the appropriate settings. We summarize results in Figure <ref> and report full results in Figures A.<ref>, A.<ref>. Preliminary results for fine-tuning also show a sizable (5-point) accuracy gap per Appendix <ref>, and more thorough investigation is left to future work.

Latency improves by up to 52.8% when exporting pruned models using , when compared with a baseline export for unconstrained pruning patterns – this baseline is described in Section <ref>. To evaluate the effectiveness of our reordering algorithm independently, we (1) apply post-training pruning to models pretrained on ImageNet; (2) export unconstrained-pruned models with and without ; and (3) benchmark the exported model's latency.  reduces latency of the exported model by 8.6% on average across all settings and yields significant latency benefits, by up to 24.9% (SqueezeNet1-1, L1), averaged across all sparsity levels – or, up to a 52.8% latency reduction at a specific sparsity level (ResNet18, FPGM). Critically, exporting unconstrained-pruned models without  actually increases latency relative to the original, unpruned model; in the same setting,  is able to realize more appropriate latency reductions.

We summarize results in Figures <ref> and <ref>, reporting full results in Figure A.<ref>. Note that there are no hyperparameters in our algorithm that can control performance, so we run our algorithm homogenously on all models to obtain said performance. We additionally plot latency for a theoretical zero-memory-copy solution, illustrating the maximum latency reduction attainable by any unconstrained pruning export; we observe that  often performs near-optimally, with latency nearly matching zero-memory-copy latency.

Setup. We use a single V100 GPU with 32 GB RAM. To export models for timing, we run an existing pruning strategy on the provided model, export using , then use PyTorch's jit trace to produce a Python-less executable. This traced model is then benchmarked using PyTorch's built-in profiling utility, including CUDA “activities” and tracking tensor memory allocation. Note this utility handles warmup automatically e.g., running several forward passes before initiating timed runs. All our latency measurements are the aggregate of 100 runs, with both mean and standard deviations reported. All accuracies are reported on the ImageNet ILSVRC 2015 [Russakovsky et al., 2015] validation dataset.

§ CONCLUSION

We introduce  () to support pruning export more generically; out of the box,  handles a predominant challenge for pruning modern neural networks: namely, memory and thus latency inefficiency. Furthermore, we introduce both a framework and an approximate solution to mitigating inefficiencies, by reducing memory copies at inference time. The end result – a generic pruning export library – expands the total surface area that existing and new pruning algorithms can operate on, by allowing any pruning pattern to be exported and making unconstrained pruning a competitive alternative to conventional, constrained pruning.

[Anwar et al., 2017]
Anwar, S., Hwang, K., and Sung, W.
Structured pruning of deep convolutional neural networks.
ACM Journal on Emerging Technologies in Computing Systems
(JETC), 130 (3):0 1–18, 2017.

[Azad & Buluç, 2017]
Azad, A. and Buluç, A.
A work-efficient parallel sparse matrix-sparse vector multiplication
In 2017 IEEE International Parallel and Distributed Processing
Symposium (IPDPS), pp.  688–697. IEEE, 2017.

[Baskaran & Bordawekar, 2009]
Baskaran, M. M. and Bordawekar, R.
Optimizing sparse matrix-vector multiplication on gpus.
IBM research report RC24704, 10 (W0812–047), 2009.

[Bengio et al., 2013]
Bengio, Y., Léonard, N., and Courville, A.
Estimating or propagating gradients through stochastic neurons for
conditional computation.
arXiv preprint arXiv:1308.3432, 2013.

[Blalock et al., 2020]
Blalock, D., Gonzalez Ortiz, J. J., Frankle, J., and Guttag, J.
What is the state of neural network pruning?
Proceedings of machine learning and systems, 2:0
129–146, 2020.

[Buluç & Gilbert, 2012]
Buluç, A. and Gilbert, J. R.
Parallel sparse matrix-matrix multiplication and indexing:
Implementation and experiments.
SIAM Journal on Scientific Computing, 340
(4):0 C170–C191, 2012.

[Courbariaux et al., 2015]
Courbariaux, M., Bengio, Y., and David, J.-P.
Binaryconnect: Training deep neural networks with binary weights
during propagations.
Advances in Neural Information Processing Systems (NeurIPS),
28, 2015.

[Frankle & Carbin, 2019]
Frankle, J. and Carbin, M.
The lottery ticket hypothesis: Finding sparse, trainable neural
International Conference on Learning Representations (ICLR),

[Frantar & Alistarh, 2022]
Frantar, E. and Alistarh, D.
Spdy: Accurate pruning with speedup guarantees.
In International Conference on Machine Learning (ICML), pp.  6726–6743. PMLR, 2022.

[Gale et al., 2019]
Gale, T., Elsen, E., and Hooker, S.
The state of sparsity in deep neural networks.
arXiv preprint arXiv:1902.09574, 2019.

[Guo et al., 2016]
Guo, Y., Yao, A., and Chen, Y.
Dynamic network surgery for efficient dnns.
Advances in Neural Information Processing Systems (NeurIPS),
29, 2016.

[Han et al., 2015]
Han, S., Pool, J., Tran, J., and Dally, W.
Learning both weights and connections for efficient neural network.
Advances in Neural Information Processing Systems (NeurIPS),
28, 2015.

[Han et al., 2016]
Han, S., Mao, H., and Dally, W. J.
Deep compression: Compressing deep neural network with pruning,
trained quantization and huffman coding.
In International Conference on Learning Representations
(ICLR), 2016.

[He et al., 2016]
He, K., Zhang, X., Ren, S., and Sun, J.
Deep residual learning for image recognition.
In Proceedings of the IEEE Conference on Computer Vision and
Pattern Recognition (CVPR), pp.  770–778, 2016.

[He et al., 2017]
He, Y., Zhang, X., and Sun, J.
Channel pruning for accelerating very deep neural networks.
In Proceedings of the IEEE International Conference on Computer
Vision (ICCV), Oct 2017a.

[He et al., 2017]
He, Y., Zhang, X., and Sun, J.
Channel pruning for accelerating very deep neural networks.
In Proceedings of the IEEE International Conference on Computer
Vision (ICCV), pp.  1389–1397, 2017b.

[He et al., 2018]
He, Y., Lin, J., Liu, Z., Wang, H., Li, L.-J., and Han, S.
Amc: Automl for model compression and acceleration on mobile devices.
In Proceedings of the European Conference on Computer Vision
(ECCV), pp.  784–800, 2018.

[He et al., 2019]
He, Y., Liu, P., Wang, Z., Hu, Z., and Yang, Y.
Filter pruning via geometric median for deep convolutional neural
networks acceleration.
In Proceedings of the IEEE Conference on Computer Vision and
Pattern Recognition (CVPR), pp.  4340–4349, 2019.

[He et al., 2022]
He, Z., Xie, Z., Zhu, Q., and Qin, Z.
Sparse double descent: Where network pruning aggravates overfitting.
In International Conference on Machine Learning (ICML), pp.  8635–8659. PMLR, 2022.

[Howard et al., 2019]
Howard, A., Sandler, M., Chu, G., Chen, L.-C., Chen, B., Tan, M., Wang, W.,
Zhu, Y., Pang, R., Vasudevan, V., et al.
Searching for mobilenetv3.
In Proceedings of the IEEE International Conference on Computer
Vision (ICCV), pp.  1314–1324, 2019.

[Huang et al., 2017]
Huang, G., Liu, Z., Van Der Maaten, L., and Weinberger, K. Q.
Densely connected convolutional networks.
In Proceedings of the IEEE Conference on Computer Vision and
Pattern Recognition (CVPR), pp.  4700–4708, 2017.

[Huang et al., 2018]
Huang, Q., Zhou, K., You, S., and Neumann, U.
Learning to prune filters in convolutional neural networks.
In IEEE Winter Conference on Applications of Computer Vision
(WACV), pp.  709–718. IEEE, 2018.

[Huang & Lee, 2021]
Huang, Z.-S. and Lee, C.-p.
Training structured neural networks through manifold identification
and variance reduction.
arXiv preprint arXiv:2112.02612, 2021.

[Iandola et al., 2016]
Iandola, F. N., Han, S., Moskewicz, M. W., Ashraf, K., Dally, W. J., and
Keutzer, K.
Squeezenet: Alexnet-level accuracy with 50x fewer parameters and< 0.5
mb model size.
arXiv preprint arXiv:1602.07360, 2016.

[Janowsky, 1989]
Janowsky, S. A.
Pruning versus clipping in neural networks.
Physical Review A, 390 (12):0 6600, 1989.

[Lee et al., 2021]
Lee, J., Park, S., Mo, S., Ahn, S., and Shin, J.
Layer-adaptive sparsity for the magnitude-based pruning.
In International Conference on Learning Representations
(ICLR), 2021.
URL <https://openreview.net/forum?id=H6ATjJ0TKdf>.

[Lee et al., 2019]
Lee, N., Ajanthan, T., and Torr, P. H.
Snip: Single-shot network pruning based on connection sensitivity.
International Conference on Learning Representations (ICLR),

[Li et al., 2017]
Li, H., Kadav, A., Durdanovic, I., Samet, H., and Graf, H. P.
Pruning filters for efficient convnets.
International Conference on Learning Representations (ICLR),

[Li et al., 2022]
Li, Y., Adamczewski, K., Li, W., Gu, S., Timofte, R., and Van Gool, L.
Revisiting random channel pruning for neural network compression.
In Proceedings of the IEEE Conference on Computer Vision and
Pattern Recognition (CVPR), pp.  191–201, June 2022a.

[Li et al., 2022]
Li, Y., Zhao, P., Yuan, G., Lin, X., Wang, Y., and Chen, X.
Pruning-as-search: Efficient neural architecture search via channel
pruning and structural reparameterization.
International Joint Conference on Artificial Intelligence
(IJCAI), 2022b.

[Lin et al., 2020]
Lin, M., Ji, R., Wang, Y., Zhang, Y., Zhang, B., Tian, Y., and Shao, L.
Hrank: Filter pruning using high-rank feature map.
In Proceedings of the IEEE Conference on Computer Vision and
Pattern Recognition (CVPR), pp.  1529–1538, 2020.

[Liu et al., 2017]
Liu, Z., Li, J., Shen, Z., Huang, G., Yan, S., and Zhang, C.
Learning efficient convolutional networks through network slimming.
In Proceedings of the IEEE International Conference on Computer
Vision (ICCV), pp.  2736–2744, 2017.

[Liu et al., 2019]
Liu, Z., Sun, M., Zhou, T., Huang, G., and Darrell, T.
Rethinking the value of network pruning.
In International Conference on Learning Representations, 2019.
URL <https://openreview.net/forum?id=rJlnB3C5Ym>.

[Louizos et al., 2018]
Louizos, C., Welling, M., and Kingma, D. P.
Learning sparse neural networks through $ l\_0 $ regularization.
International Conference on Learning Representations (ICLR),

[Miao et al., 2021]
Miao, L., Luo, X., Chen, T., Chen, W., Liu, D., and Wang, Z.
Learning pruning-friendly networks via frank-wolfe: One-shot,
any-sparsity, and no retraining.
In International Conference on Learning Representations
(ICLR), 2021.

[Molchanov et al., 2017]
Molchanov, D., Ashukha, A., and Vetrov, D.
Variational dropout sparsifies deep neural networks.
In International Conference on Machine Learning (ICML), pp.  2498–2507. PMLR, 2017a.

[Molchanov et al., 2017]
Molchanov, P., Tyree, S., Karras, T., Aila, T., and Kautz, J.
Pruning convolutional neural networks for resource efficient
International Conference on Learning Representations (ICLR),

[Narang et al., 2017]
Narang, S., Undersander, E., and Diamos, G.
Block-sparse recurrent neural networks.
arXiv preprint arXiv:1711.02782, 2017.

[Reed, 1993]
Reed, R.
Pruning algorithms-a survey.
IEEE transactions on Neural Networks, 40 (5):0
740–747, 1993.

[Russakovsky et al., 2015]
Russakovsky, O., Deng, J., Su, H., Krause, J., Satheesh, S., Ma, S., Huang, Z.,
Karpathy, A., Khosla, A., Bernstein, M., et al.
Imagenet large scale visual recognition challenge.
International Journal of Computer Vision (IJCV), 1150
(3):0 211–252, 2015.

[Savarese et al., 2020]
Savarese, P., Silva, H., and Maire, M.
Winning the lottery with continuous sparsification.
Advances in Neural Information Processing Systems (NeurIPS),
33:0 11380–11390, 2020.

[Shang et al., 2022]
Shang, H., Wu, J.-L., Hong, W., and Qian, C.
Neural network pruning by cooperative coevolution.
arXiv preprint arXiv:2204.05639, 2022.

[Srinivas et al., 2017]
Srinivas, S., Subramanya, A., and Venkatesh Babu, R.
Training sparse neural networks.
In Proceedings of the IEEE conference on computer vision and
pattern recognition workshops, pp.  138–145, 2017.

[Sze et al., 2017]
Sze, V., Chen, Y.-H., Yang, T.-J., and Emer, J. S.
Efficient processing of deep neural networks: A tutorial and survey.
Proceedings of the IEEE, 1050 (12):0
2295–2329, 2017.

[Tan & Le, 2021]
Tan, M. and Le, Q.
Efficientnetv2: Smaller models and faster training.
In International Conference on Machine Learning (ICML), pp.  10096–10106, 2021.

[Tan et al., 2019]
Tan, M., Chen, B., Pang, R., Vasudevan, V., Sandler, M., Howard, A., and Le,
Q. V.
Mnasnet: Platform-aware neural architecture search for mobile.
In Proceedings of the IEEE Conference on Computer Vision and
Pattern Recognition (CVPR), pp.  2820–2828, 2019.

[Vuduc et al., 2005]
Vuduc, R., Demmel, J. W., and Yelick, K. A.
Oski: A library of automatically tuned sparse matrix kernels.
In Journal of Physics: Conference Series, volume 16, pp.  521. IOP Publishing, 2005.

[Wang et al., 2022]
Wang, H., Qin, C., Bai, Y., Zhang, Y., and Fu, Y.
Recent advances on neural network pruning at initialization.
In International Joint Conference on Artificial Intelligence
(IJCAI), pp.  23–29, 2022.

[Wen et al., 2016]
Wen, W., Wu, C., Wang, Y., Chen, Y., and Li, H.
Learning structured sparsity in deep learning.
In Advances in Neural Information Processing Systems
(NeurIPS), 2016.

[Xiao et al., 2019]
Xiao, X., Wang, Z., and Rajasekaran, S.
Autoprune: Automatic network pruning by regularizing auxiliary
Advances in Neural Information Processing Systems (NeurIPS),
32, 2019.

[Yamamoto & Maeno, 2019]
Yamamoto, K. and Maeno, K.
Pcas: Pruning channels with attention statistics for deep network
Proceedings of the British Machine Vision Conference (BMVC),

[Yu et al., 2022]
Yu, S., Mazaheri, A., and Jannesari, A.
Topology-aware network pruning using multi-stage graph embedding and
reinforcement learning.
In International Conference on Machine Learning (ICML), pp.  25656–25667. PMLR, 2022a.

[Yu et al., 2022]
Yu, X., Serra, T., Ramalingam, S., and Zhe, S.
The combinatorial brain surgeon: Pruning weights that cancel one
another in neural networks.
In International Conference on Machine Learning (ICML), pp.  25668–25683. PMLR, 2022b.

[Zhu & Gupta, 2017]
Zhu, M. and Gupta, S.
To prune, or not to prune: exploring the efficacy of pruning for
model compression.
arXiv preprint arXiv:1710.01878, 2017.

On the left, we show post-training pruned accuracy, with no fine-tuning. In the middle, we show only sparsity level 50% but for fine-tuned accuracies over each epoch. This shows that the fine-tuned models have mostly converged. On the right, we show accuracies across sparsity levels, after fine-tuning for 5 epochs. In short, unconstrained still outperforms constrained after fine-tuning.

§ HOW FINE-TUNING AFFECTS CONSTRAINT IMPACT ON ACCURACY

We note that the gap between unconstrained and constrained pruning remains significant ($>5$ points on ImageNet) even after fine-tuning.

We channel prune DenseNet121 at 10%, 20%, 30%, 40%, 50% parameter sparsity using the LAMP heuristic — using both the constrained variant and an unconstrained variant. We then fine-tune all 10 models for 5 epochs each. These experiments show that unconstrained accuracy still significantly outperforms constrained accuracy on ImageNet. We show results in Figure <ref>, from which we can make the following conclusions:

* After fine-tuning, unconstrained outperforms constrained by up to 6 ImageNet validation points.

* Unconstrained accuracy is almost independent of the pruning level, suggesting that constraints may hinder fine-tuned accuracy.

* We observe throughout training that unconstrained accuracy converges much quicker than constrained accuracy, so removing constraints can lower fine-tuning cost.

Note that, the accuracy of the pruned model depends on many factors, including the dataset/task, pruning strategy, training strategy, model structure, etc. Therefore, it is hard to justify if unconstrained pruning always outperforms constrained pruning in terms of accuracy. Our major contribution was to provide a method/tool () that is able to speed up any pruning methods (i.e., to bridge the latency gap between constrained pruning and unconstrained pruning). With the proposed , when designing a pruning method, we will only need to focus on the accuracy without worrying the latency regression brought by memory copies.

§ HOW REORDERING REDUCES MEMORY COPIES

There are several cases, with various degrees of complexity, for consumer interactions. In each scenario, we can use reordering to minimize the number of memory copies. See Figure A.<ref> for the architecture.

* Case 1: Disjoint sets. Say convolution $B$ retains channels 1 and 3. Convolution $C$ retains channels 2 and 4. To minimize memory copies, ensure each convolution's retained channels are side-by-side in the output tensor $X$. To do so, we rearrange the filters in convolution $A$ to be 1, 3, 2, 4. This means the channels in $X$ are also rearranged to be 1, 3, 2, 4. Notice the channels $B$ retains – 1, 3 – are now contiguous in memory in the first two channels of $X$. Channels $C$ retains – 2, 4 – are contiguous in the last two channels of $X$. Now, no memory copies are needed at inference time, as convolution $B$ takes the first two channels $X[:2]$ and $C$ takes the last two $X[2:]$. (Figure <ref>, Case 1)

* Case 2: Overlapping sets. Say convolution $B$ retains channels 1 and 3. Convolution $C$ retains channels 2 and 3. Again, ensure each convolution's retained channels are side-by-side in $X$. To do so, rearrange the filters in convolution $A$ to be 1, 3, 2. More generally, include channels unique to $B$, then channels shared by $B$ and $C$, then channels unique to $C$. Now, the channels $B$ retains – 1, 3 – are contiguous and channels $C$ retains – 2, 3 – are contiguous. However, for convolution $C$, notice $X$ contains channels in the reverse order: 3, 2 in stead of 2, 3. As a result, we also need to reorder input channels in convolution $C$ to be 3, 2. Now, no memory copies are needed at inference time, as $B$ uses $X[:2]$ as input and $C$ uses $X[2:]$. (Figure <ref>, Case 2)

* Case 3: Unsolvable sets. Say convolution $B$ retains channels 1, 3, 4. Convolution $C$ retains channels 2, 3, 4. We introduce another convolution $D$, which retains channels 1, 2. There is no ordering of channels that would completely eliminate memory copies, as satisfying any pair of convolutions would necessarily exclude the remaining convolution. We will formalize the definition of this unsolvable case later. For now, our intuition is to instead maximize the number of channels placed in the correct order. This means satisfying convolutions $B$ and $C$ and ignoring convolution $D$, since convolutions $B$ and $C$ each retain 3 channels and convolution $D$ retains only 2 channels.

Step 1 - Divide architecture into segments that can be independently pruned. At the top, we illustrate a ResNet building block, with convolutions $A, B, C, D$. This block contains two segments, illustrated as i. in the middle row and ii. in the bottom row. Within each segment, a convolution is either a producer that produces output (purple) or a consumer that consumes input (blue). This is better illustrated in the “canonical” figures on the right, which places all producers on the left and consumers on the right.

Step 2 - Translate each segment into a graph. Only consumers (blue box) are translated into nodes (gray circles). The blue numbers (ex. 1,3 in i.) are the channels each consumer retains. The gray numbers (e.g., 2 in i.) are the node and edge reward. Examples i, ii, iii are ResNet segments from Figure <ref>. (i) Since C retains two channels, its node has a reward of 2. (ii) B retains 1,3 and D retains 2,4; since both nodes retain two channels, their reward are each 2. They do not share channels so do not share an edge. (iii) B retains 1,3 and D retains 2,3; since both nodes retain channel 2, they share an edge with reward -1. (iv.) All nodes are densely connected, because every convolution shares channels with all other nodes.

Step 3 - Translate graph into channel ordering. Find maximum reward acyclic paths. Then, translate paths into a channel ordering. Examples i, ii, iii are ResNet segments from Figure <ref>. (i) There is only one node, so order its channels arbitrarily. (ii) Since there are no edges, there are two single-node paths. Order path 1 node's channels (purple), then path 2 node's channels (blue). (iii) There is one path with both nodes. Order B-only channels (1, purple), B-and-D shared channels (3, purple-blue), then D-only channels (2, blue). (iv) Since all three nodes are densely connected, the first path can only contain two of three nodes. The two nodes with the highest reward are D and E, each with reward three, so they comprise path 1. B comprises path 2. Per path 1, take E-only channels (1, 2, blue), then E-D shared channels (0, blue-purple), then D-only channels (3, 4, purple). All channels in the second path are already covered by the ordering, so the ordering is complete.

Step 4 - Reorder weights. ii, iii correspond to ii, iii in previous figures. (ii) The final ordering dictates the ordering for producer $A$ and $C$. However, producer $C$ omits 1,3 as none of its consumers ($D$) use those channels. Consumers $B$ and $D$ do not need reordering, as their retained channels 1,3 and 2,4 were not reordered. (iii) Consumer $B$ does not need reordering, as the final ordering lists its channels 1,3 in order. However, consumer $D$ needs to reorder its channels from 2,3 to 3,2.

§ HOW GRAPH ALGORITHM SOLVES REORDERING

For the three cases in the previous section, Appendix <ref>, here is how our graph would be constructed and how the solution path minimizes memory copies (Figures <ref>,<ref>,<ref>,<ref>).

* Case 1: Disjoint Sets. In the simplest case, no convolutions share retained channels, so when rearranging channels, place all channels retained by one convolution together, then all channels retained by a second convolution etc. Any ordering of convolutions works. Translated into our graph: There are no edges, and we can pick any ordering of nodes. The ordering of nodes then directly corresponds to an ordering of channels.

* Case 2: Overlapping Sets. Say we have a linear ordering of convolutions, where each convolution shares retained channels only with the preceding and succeeding convolutions. In this case, there always exists a zero-copy solution: start with channels unique to the first convolution, channels shared between the first and second, channels unique to the second convolution, channels shared between the second and third etc. Translated into our graph: Find a set of nodes where each node has at most two neighbors – in other words, an acyclic path.

* Case 3: Unsolvable Sets. Say one or more convolutions share retained channels with all other convolutions. This means we have a cycle: Attempting to order the nodes linearly will result in one node belonging at both the end and the start at the same time. In other words, we cannot achieve a perfect zero-memory-copy solution. In this case, our goal is to maximize the number of channels that don't need to be copied. Translated into our graph: Assign a reward to every node and edge. Every node's reward is the number of channels the corresponding convolutions retains. Every edge's reward is negative of the number of shared channels between the two node's convolutions. This way, a path's reward corresponds to the number of channels included in that path. To maximize the number of copy-free channels, minimize the path reward. In short, find the maximum reward acyclic path.

How to fix inefficient memory copies for pruned multi-branch segments? To avoid memory copies at inference time reorder producer weights as shown in green above. This ensures that the two consumers (purple and pink) take as input contiguous slices of the green output tensor. Since these slices are already contiguous in memory, no memory copies are needed to assemble the pair of consumer inputs.

A segment is made up of (a) convolutions that have their outputs combined (e.g., summed or concatenated), along with (b) all the convolutions that use those values. We call the convolutions producing output producers and the convolutions consuming values consumers. We define a single-branch segment (left) to be a part of the architecture that includes just one convolution producing output and one convolution consuming input. We define a multi-branch segment (right) to be a part of the architecture that contains multiple convolutions producing outputs or multiple convolutions consuming inputs.

§ HANDLING NODE SUBSETS

Recall each node is equivalent to a convolution. In particular, each node represents the set of retained channels for a convolution. Some nodes may be strict sets of another node: For example, one node $A$ may correspond to retained channels 1, 2, 3. Call this the parent. However, two other nodes may correspond to channels 1, 2 ($B$); and 2, 3 ($C$). Call these the child nodes. Although there exists a cycle between $A, B, C$, there exists a valid channel ordering: 1, 2, 3.

As a result, nodes with parent-child relationships break the requirement for an acyclic path. One possibility is to simply drop parent or child nodes, to ensure retain the acyclic path requirement. However, parent node neighbors may influence within-parent channel ordering, which conflicts with the ordering imposed by child nodes. Here are two examples:

* Child nodes cannot be ignored. One natural idea is to include only the parent node in the graph and drop all child nodes. Here is a counterexample: Say there are nodes $A$, $B$, $C$. $A$ retains 1, 2, 3. $B$ retains 2, 3, 4, 5. $C$ retains 4, 5, 6. The ordering is straightforward: $A \rightarrow B \rightarrow C$, inducing the order 1, 2, 3, 4, 5, 6. However, say there also exists child nodes $D$, which retains 3, 4, 5 and $E$, which retains 2, 3, 5. By ignoring $D, E$ and using $B$, we incur more memory copies. Instead, the algorithm should including the two child nodes, ordering $A \rightarrow D \rightarrow E \rightarrow C$, inducing the order 1, 2, 3, 5, 4, 6.

* Parent nodes cannot be ignored: . Another natural idea is to include only the child nodes in the graph and drop all parent nodes. However, parent nodes are only automatically accounted for if enough child nodes are used to cover all channels retained by the parent node. In any other case, the algorithm must choose between child nodes or the parent node. For example, say we have nodes $A, B, C$, which retain 1, 2, 3, 4; 2, 3, 4, 5; and 4, 5, 6, respectively. Then, child nodes $D, E$ retain 2, 4, 5; and 2, 3, 5. There are 3 options here: $A \rightarrow B \rightarrow C$ or $A \rightarrow D \rightarrow C$ or $A \rightarrow E \rightarrow C$. The maximum reward path is actually the one that includes the parent node $B$.

Knowing this, our only option left is to include both child and parent nodes in the graph. Instead, we introduce two modifications:

* Permit cycles between parent and child nodes.

* Modify the reward function.

We can modify the reward functions in the following way, by breaking down all possible ways to incorporate parent-child nodes in the solution path.

* If select child nodes after selecting parent

* Parent contributes to reward regardless of how you leave the parent's group of child nodes. (no modification needed)

* If select child nodes without selecting parent

* Parent contributes to reward if you leave by selecting the parent (no modification needed)

* Alternatively, tour enough children nodes to cover the parent node's channels, to contribute to the reward.

As a result of this breakdown, we only need to modify the reward if enough child nodes are toured to cover the parent node's channels. In other words: If included child nodes include all channels for the parent node, then the parent node's reward is automatically added to the path's reward. If otherwise, the parent node contributes to the reward normally, depending on its participation in the maximum-reward path.

§ REDUCTION TO SINGLE PRODUCER

To reduce the multiple-producer case to the single-producer case, we make two critical assumptions, for operations other than a multiply-reduce:

* Producer channels are not “mixed” with other channels from the same producer. Here, channels $i$ and $j$ are “mixed” if they both affect one output channel. For example $y = x[:, i] + x[:, j]$ would “mix” both channels $i$ and $j$. Using this definition of “mix”: our assumption is that channel $i$ from any producer is never mixed with channel $j \neq i$ from that same producer. This does not preclude channel $i$ from mixing with itself. This is generally a true assumption, as channel mixing in common architectures is parameterized as a multiply-reduce. Note that neither channel shuffling nor transformers would violate this assumption.

* If producer $A$ mixes with producer $B$, exactly one channel from $A$ mixes with exactly one channel from $B$. We assume that producer outputs are mixed relatively simply without channel micro-management. This is generally a true statement in common architectures as well, as the only channel-related operations like  only increase the number of feature map channels associated with a producer channel.

Given the two above assumptions, we can then establish an equivalence class of channels across producers. In particular, we can define a one-to-one mapping from producer $A$'s $i$th channel to producer $B$'s $j$th channel and repeat this for all channels. With this mapping constructed, we can then (1) reduce the multi-producer case to the single-producer case by replacing $B.j$ with $A.i$, (2) run the single-producer, multi-consumer algorithm, then (3) use the order of producer $A$'s channels to determine the ordering of producer $B$'s channels.

If we have a concatenation operation, as opposed to an addition for example, then we simply treat every producer independently, as there are no cross-producer constraints.

§ UNCONSTRAINED OUTPUT PRUNING

The main text describes unconstrained input pruning in detail but omits a description of the output pruning algorithm. We note empirically that input pruning outperforms output pruning (Figures <ref>, <ref>). There are several subtleties in exporting an unconstrained output-pruned model. Like before, memory copies are an issue, but rather than copy channels to produce input for the subsequent convolution, the memory copies now stem from assembling incompatible convolutional outputs.

Input vs. Output Pruning Accuracy (Part 1) Input pruning (blue) outperforms output pruning (purple) in accuracy.

Input vs. Output Pruning Accuracy (Part 2) Input pruning (blue) outperforms output pruning (purple) in accuracy.

Say we have two convolutions $A$ and $B$. Both outputs have 4 channels and are summed together. There are several possible pruning patterns and associated problems:

* Convolution $A$ prunes channel 2. Now, the two outputs feature incompatible dimensions.

* Convolution $A$ prunes channel 2, and convolution $B$ prunes channel 3. The two outputs feature compatible dimensions, but naively summing the two tensors is incorrect.

To resolve this, the naive solution is to infill zeros, but this incurs a large number of memory copies. This infilling operation is the naive baseline for output pruning latency.

Instead, we can sum all channels that both convolutions $A$ and $B$ both retain. Then, we can concatenate with channels unique to $A$ and $B$ each. This is reminiscent of unconstrained input pruning: Reorder filters in $A$ and $B$ to place channels unique to $A$ first, then channels shared by $A$ and $B$, then channels unique to $B$. This is exactly how we order channels for unconstrained pruning.

To support unconstrained output pruning, we define each node in the graph to be a convolution producing output – as opposed to a convolution consuming input, as in unconstrained input pruning. Then, add edges when those convolutions retain the same channels. The remainder of the algorithm remains the same.

Note that output pruning is sensitive to a correctness issue: “pruned” channels do not stay “pruned”, as zero is not idempotent under operations such as a bias. This makes a general purpose export for output pruning slightly more tricky.

§ REORDERING PIPELINE EXAMPLE

Here is the full reordering pipeline. For a more formal description, see Algorithm <ref> in the main text. Reuse the same example as above: There is one convolution $A$ producing 4 channels. Convolution $B$ retains channels 1, 3, 4; $C$ retains channels 2, 3, 4; and $D$ retains channels 1 and 4.

* Build a graph: every node contains channels retained by the corresponding convolution. Create edges between nodes when their convolutions share retained channels. We have 3 nodes, labeled $B$, $C$, and $D$. All 3 nodes are densely connected.

* Find the maximum reward acyclic path. Every node corresponds to a convolution, so the path admits a convolution ordering. In this case, our algorithm computes path $B \rightarrow C$, excluding $D$.

* This convolution ordering admits a channel ordering: Start with channels unique to the first convolution, then channels shared between the first and second convolution, the channels unique to the second convolution etc. We then write the channel ordering: (1), (3, 4), (2). We use parentheses to denote channels unique to $B$, those shared by $B$ and $C$, then those unique to $C$.

* Use this ordering to reorder filters in the convolution producing output. Output channels – , the filters – in $A$ are rearranged as 1, 3, 4, 2.

* Use this ordering to reorder filters in all convolutions consuming the reordered tensor. Input channels for $B$ are left in the same order, as 1, 3, 4. Input channels for $C$ are reordered to be 3, 4, 2.

Model       Stat        Segments       10%       20%       30%       40%       50%       60%       70%       80%       90%

ResNet18                  FLOPs      All (ours)      1.60      1.36      1.13      0.93      0.71      0.52      0.34      0.19      0.07

ResNet18                    Acc      All (ours)     54.88     51.94     51.00     49.75     45.24     39.94     31.07     19.34     10.27

ResNet18                  FLOPs          Single-branch      1.41      0.99      0.57      0.17      0.16      0.16      0.16      0.16      0.16

ResNet18                    Acc          Single-branch     54.50     49.87     41.61      8.77      8.28      7.49      8.38      8.64      9.23

MobileNetV3-Small         FLOPs      All (ours)      0.05      0.04      0.04      0.03      0.02      0.02      0.01      0.01      0.00

MobileNetV3-Small           Acc      All (ours)     59.32     55.06     51.34     41.67     34.46     24.20     15.30     10.03      3.68

MobileNetV3-Small         FLOPs          Single-branch      0.05      0.04      0.04      0.04      0.04      0.04      0.04      0.04      0.04

MobileNetV3-Small           Acc          Single-branch     55.33     37.35      0.10      0.15      0.11      0.10      0.10      0.11      0.12

MobileNetV3-Large         FLOPs      All (ours)      0.19      0.16      0.13      0.11      0.08      0.06      0.04      0.02      0.01

MobileNetV3-Large           Acc      All (ours)     64.23     62.82     59.81     56.55     49.79     41.03     27.30     18.75      8.14

MobileNetV3-Large         FLOPs          Single-branch      0.18      0.15      0.14      0.14      0.14      0.14      0.14      0.14      0.14

MobileNetV3-Large           Acc          Single-branch     63.84     55.08      0.13      0.14      0.16      0.16      0.14      0.16      0.16

EfficientNetV2-Small      FLOPs      All (ours)      2.47      2.08      1.69      1.34      0.98      0.69      0.41      0.19      0.06

EfficientNetV2-Small        Acc      All (ours)     67.92     66.25     65.53     62.77     59.66     54.16     44.80     33.36     20.04

EfficientNetV2-Small      FLOPs          Single-branch      2.24      1.61      1.43      1.43      1.43      1.43      1.43      1.43      1.43

EfficientNetV2-Small        Acc          Single-branch     67.40     59.85      0.27      0.32      0.33      0.31      0.31      0.28      0.31

Accuracy vs. FLOPs with Fine-Tuning. “Single-branch” means we prune only single-branch segments in the network to attain the desired compression ratio. “All” means we pruned all segments – single-branch and multi-branch – to reach the desired compression ratio. Across all models, pruning all segments achieves a better accuracy-latency tradeoff curve.

Single-branch segments account for fewer and fewer of the convolutions over time: Decreasing numbers of convolutions in neural network architectures belong to a single-branch segment, starting from 65% with the advent of ResNets (2015) and decreasing to 26% with models like EfficientNet (2019). Due to this, pruning export algorithms must accommodate multi-branch portions of the architecture.

Single-branch segments make up less and less of the total latency over time: We prune the maximum number of channels in only single-branch segments, which prior methods can export; just as with FLOP count, single-branch methods can prune less and less of the total latency over time, only able to prune 4.9% of the total latency for MobileNet-V3. By contrast, by pruning all the segments that  algorithm can export – meaning all segments – we are able to reduce a further 15% of latency on average.

Model     Method     Latency     Accuracy

ResNet18     L2     3.74     54.5%

ResNet18         3.45     54.9%

ResNet18     L2     3.60     49.9%

ResNet18         2.54     49.8%

MobileNetV3-Small     L2     1.84     37.3%

MobileNetV3-Small         1.79     51.4%

Accuracy vs. Latency for Magnitude Pruning: A summary of accuracy-latency tradeoffs between pruning simple segments only (L2) compared with pruning all segments (L2-). In the latter, since we additionally prune multi-branch segments, we use  to export the model for final latency measurements. Across various model sizes and sparsity levels, we find that models using  attain lower latency and comparable or higher accuracy.

Single-branch segments make up less and less of the FLOP count over time: Across models over the past decade, single-branch segments make up precipitously less and less of the total FLOP count, only accounting for 6.5% of the total computational cost for EfficientNet. By contrast, by pruning all the segments that our  algorithm can export – meaning all segments – we are able to prune 99.5% of the computational cost, on average.

§ IMPORTANCE OF MULTI-BRANCH SEGMENTS

One possible way to handle multi-branch segments is to completely ignore them. In this appendix section, we explore this possibility.

Unfortunately, this strategy is not viable: Over time, less and less computational complexity in a neural network is due to single-branch segments. More and more are involved in multi-branch segments of a neural network. This is for good reason, as this has significant impact on accuracy: Pruning 10% of all weights is more difficult when you're restricted to just single-branch segments. We show this in Figures <ref>,<ref>,<ref> and Tables <ref>,<ref>.

Single-branch segments account for as little as 4.9% of latency, 6.5% of FLOPs and 26% of convolutions for modern, efficient models. We could focus on train-time pruning performance for single-branch segments, but for compact, efficient models, only a small percentage of latency is due to single-branch segments. As a consequence, this approach is bottlenecked, being able to prune only a small percentage of latency in more modern neural networks–as little as 4.9% of latency in MobileNetV3-Small (Figure <ref>), 6.5% of FLOPs in EfficientNet-B7 (Figure <ref>), and 26% of the convolutions in MobileNetV3-Large (Figure <ref>).

Algorithms obtain “free” improvements by pruning multi-branch segments using our export, of up to 14.1% accuracy points and 29.4% latency. We assess this improvement by comparing single-branch pruning performance against “our” method: (1) Prune all segments in the model, instead of only single-branch segments; (2) Fine-tune for 1 epoch on ImageNet; (3) Evaluate for accuracy, and benchmark both models for latency. This allows us to make an accuracy-latency comparison. We show accuracy-latency tradeoff curves on GPU (Figure <ref>, Table <ref>).

To break down these accuracy-latency tradeoff curves above, we show that (1) accuracy improves when we additionally prune multi-branch segments and (2) latency improves when we use reordering to export multi-branch segments.

Accuracy improves by up to 45% when additionally pruning multi-branch segments. We assess the impact of additionally pruning multi-branch segments: Prune all segments, including multi-branch ones; run a previously-developed pruning algorithm; fine-tune for 1 epoch; and assess accuracy. We evaluate on a number of modern and baseline neural networks, showing a better accuracy-FLOPs tradeoff curve, by supporting pruning for multi-branch segments. Note that the pruning algorithm itself remains constant; the only change is which part of the network we prune. We find that pruning all segments – instead of pruning only single-branch segments – incurs up to a 45-point increase in accuracy or 14$\times$ reduction in FLOPs (
Table A.<ref>), since single-branch segments account for a limited percentage of the total computational cost (Figure <ref>). We also report results without fine-tuning, computing accuracy directly on the post-training pruned network (Figure A.<ref>, Table A.<ref>). Above, we report FLOPs to examine the effects of segment choice independently. For completeness, we also analyze tradeoffs using latency, using our reordering algorithm for export (Figure A.<ref>).

Taken together, the ablations above explain the accuracy-latency improvements.

5cAccuracy     5cGFLOPs

Model     Pruning     1%     5%     10%     20%     30%     1%     5%     10%     20%     30%

MobileNetV3-Small     Ours (All)     66.67%     51.71%     21.98%     0.45%     –     0.0537     0.0516     0.0487     0.0421     –

MobileNetV3-Small     Single-branch     66.01%     34.04%     0.89%     0.08%     –     0.0534     0.0503     0.047     0.0413     –

MobileNetV3-Large     Ours (All)     73.70%     –     46.91%     0.35%     0.017%     0.2133     –     0.1883     0.1608     0.1332

MobileNetV3-Large     Single-branch     73.34%     –     1.56%     0.09%     0.010%     0.2119     –     0.1845     0.1548     0.1392

Accuracy vs. FLOPs without Fine-tuning: Above we compare end-to-end the accuracy-FLOPs impact of our method; this includes (1) pruning all instead of just single-branch segments and (2) using our export strategy that includes reordering weights. The percentages x% denote what percent of channels we pruned from the total number of channels in the network. However, note that Ours (All) and Single-branch under the same percentage are not fully comparable, due to the slightly variable FLOPs shown to the right. As a result, we suggest referencing Figure <ref> for a visual tradeoff curve.

Accuracy vs. FLOPs without Fine-Tuning for Single vs. Multi-branch Segments: Existing pruning algorithms obtain a more favorable accuracy-computation trade off. Note that lower FLOPs (left) and higher accuracy (top) is preferred, so tradeoff curves closer to the top-left are preferred. In particular, pruning all segments attains higher accuracy than pruning single-branch segments only, under the same FLOP budget. Results are obtained using L2-magnitude pruning and without fine-tuning. See Table A.<ref> for numerical results.

Accuracy vs. FLOPs with Fine-Tuning for Single vs. Multi-branch Segments: Using , existing pruning algorithms obtain a more favorable accuracy-latency trade off. Note that lower latency (left) and higher accuracy (top) is preferred, so tradeoff curves closer to the top-left are preferred. In particular, pruning all segments attains higher accuracy than pruning single-branch segments only, under the same latency budget. Furthermore, employing our export algorithm ensures that that the final exported, pruned model achieves latency reductions. Results are obtained using L2-magnitude pruning and with fine-tuning.

Accuracy vs Latency with L2-Magnitude Pruning for Single vs. Multi-branch Segments This shows tradeoff curves for pruning only single-branch segments of a network (blue), comparing that with pruning all segments – including multi-branch – segments of a network (orange). The accuracy-latency tradeoff curve for pruning all segments is more favorable.

§ UNCONSTRAINED INPUT PRUNING ACCURACY

This section contains the full set of results for unconstrained input pruning across all models, sparsity levels, and heuristics. These are split between two large grids of figures (Figures <ref> and <ref>), where we observe that unconstrained accuracy generally matches or outperforms constrained accuracy. We report numerical results in Tables A.<ref>, A.<ref>, A.<ref>.

§ UNCONSTRAINED INPUT PRUNING LATENCY

This section contains the full set of results for unconstrained input pruning export latency across all models, heuristics, and sparsity levels. We plot the results in A.<ref> and include the results in table-form in Tables A.<ref>, A.<ref>, A.<ref>.

Unconstrained vs. constrained accuracy. In the vast majority of cases, unconstrained accuracy matches or outperforms constrained accuracy. See numeric results for these plots in Tables A.<ref>, A.<ref>, A.<ref>.

Unconstrained vs. constrained accuracy In the vast majority of cases, unconstrained accuracy matches or outperforms constrained accuracy. See numeric results for these plots in Tables A.<ref>, A.<ref>, A.<ref>.

Export latency for our unconstrained export, baseline unconstrained export, and the optimal zero-copy export. Notice that  (solid) approaches the optimal (dotted) latency fairly often. See numeric results for these plots in Tables A.<ref>, A.<ref>, A.<ref>.