# The Need for Speed
Pruning Transformers with One Recipe

Samir Khaki , Konstantinos N. Plataniotis
Department of Electrical and Computer Engineering
University of Toronto
Toronto, Canada
<EMAIL_ADDRESS>Project Page: http://www.samirkhaki.com/optin-
transformer-pruning/

###### Abstract

We introduce the One-shot Pruning Technique for Interchangeable Networks
(OPTIN) framework as a tool to increase the efficiency of pre-trained
transformer architectures, across many domains, without requiring re-training.
Recent works have explored improving transformer efficiency, however often
incur computationally expensive re-training procedures or depend on
architecture-specific characteristics, thus impeding practical wide-scale
adoption across multiple modalities. To address these shortcomings, the OPTIN
framework leverages intermediate feature distillation, capturing the long-
range dependencies of model parameters (coined trajectory), to produce state-
of-the-art results on natural language, image classification, transfer
learning, and semantic segmentation tasks. Our motivation stems from the need
for a generalizable model compression framework that scales well across
different transformer architectures and applications. Given a FLOP constraint,
the OPTIN framework will compress the network while maintaining competitive
accuracy performance and improved throughput. Particularly, we show a $\leq
2\%$ accuracy degradation from NLP baselines and a $0.5\%$ improvement from
state-of-the-art methods on image classification at competitive FLOPs
reductions. We further demonstrate the generalization of tasks and
architecture with comparative performance on Mask2Former for semantic
segmentation and cnn-style networks. OPTIN presents one of the first one-shot
efficient frameworks for compressing transformer architectures that
generalizes well across multiple class domains, in particular: natural
language and image-related tasks, without re-training. Code is available at:
https://github.com/Skhaki18/optin-transformer-pruning.

##  1 Introduction

The inception of transformer architectures (Vaswani et al., 2017) marked the
beginning of a new era in deep learning, since affecting various domains
including natural language processing (Kenton & Toutanova, 2019), and vision-
related tasks (Dosovitskiy et al., 2021). The transformers’ straightforward
design has enabled extensive applications to a variety of challenging
problems, but it also brings a major drawback: high computational costs (Yu &
Xiang, 2023). The computational resources required for training and
inferencing with a transformer are often quite significant and pose a real
impediment to wide-scale adoption, especially in resource-constrained
environments, such as edge devices (Wang et al., 2020a). Recent works have
proposed methods including quantization (Xiao et al., 2023), pruning (Ma et
al., 2023), and knowledge distillation (Hao et al., 2022) to address this
bottleneck, similarly explored in convolutional neural networks (CNN)
compression (Li et al., 2017).

Despite much success in compressing CNNs, transformer architectures contain
significant differences in their structure, often causing impediments for
methods that work well in the former domain (Kwon et al., 2022; Yu & Xiang,
2023; Yang et al., 2023). Due to the massive size of Transformer models, some
works have introduced various methods of compression, which can be loosely
divided into one-shot and iterative (Zhang et al., 2022). One-shot methods
generally consist of a pruning phase followed by re-training to recover the
lost generalization performance, meanwhile, iterative processes can account
for the training dynamics in model compression (Zhang et al., 2022).
Unfortunately, in the past, both methods have often been limited to a
particular architecture/task or required significant resources in the pruning
and re-training processes. For user models that have already endured the
expensive cost of training, there exists limited options for fast model
compression (Kwon et al., 2022) that can be easily realized on standard
hardware for different types of transformer architectures. The lack of a
general approach to transformer pruning across multiple tasks and modalities
provides sufficient motivation for the introduction of a unified framework;
hence we introduce one of the first one-shot model compression techniques that
generalize well over multiple tasks and architectures without incurring the
cost of re-training.

In this work, we introduce the One-shot Pruning Technique for Interchangeable
Networks (OPTIN) framework to efficiently compress modern transformers. The
novelty is in its generalizability across domains and tasks, and its ability
to produce competitive models without requiring re-training, thus enabling
future application to larger models across many tasks. We apply OPTIN to
natural language, and vision-related tasks, showing competitive performance
with SoTA in these cases.

Our primary contribution rests on the ability of our OPTIN framework to
produce transformers with competitive performance at reduced computational
loads (FLOPs) across various task domains and architectures, that can be
realized on standard hardware. In particular, we demonstrate superior
performance on a variety of tasks in Language 4.1), Vision (Sec 4.2), and
Application tasks (Sec 4.3), while maintaining competitive compression rates,
without incurring the cost of re-training. Finally, we execute several
extensive experiments from framework-specific settings to applications on
transfer-learning and CNN networks to demonstrate OPTIN’s robustness and
generalizability over the task and architecture (Sec 3\- 4.3).

##  2 Related Works

Due to the diversity of architectures and tasks discussed in our work, the
following review of state-of-the-art methods provides an overview of efficient
transformer design followed by recent developments in both language and vision
domains.

Domain Specific Design of Efficient Transformers Transformers have enabled
significant progress in the field of NLP (Vaswani et al., 2017; Kenton &
Toutanova, 2019) and Computer Vision (Dosovitskiy et al., 2021; Liu et al.,
2021a).

Efficiency improvements in transformers have stemmed from a variety of
approaches including exploring hybrid architectures (Liu et al., 2021a),
quantization techniques (Kim et al., 2021), knowledge distillation (Hao et
al., 2022), and model pruning (Pan et al., 2021).

Recently, TorchPruning (Fang et al., 2023) explored the application of multi-
domain pruning by creating an inter-architecture dependency map, while UPop
(Shi et al., 2023) introduced a unified pruning method for combined vision-
language models. However, these methods have limitations, including
architecture-specific dependencies and expensive re-training policies
generally impeding wider-scale industry use (Fang et al., 2023). In contrast,
our approach leverages intermediate feature distillation to compress pre-
trained transformers in one shot across both language and vision-related
tasks. Notably, our method operates effectively without re-training and scales
well over a variety of complex architectures and task domains.

Compressing Language Transformers Several structured pruning methods have been
introduced to compress models in the language domain. Attention Head pruning
(Michel et al., 2019) explored the dynamics of attention heads across a
transformer architecture to determine their individual impact on performance.
Block-wise pruning (Lagunas et al., 2021) was motivated by removing block
structures from weights under the movement pruning (Sanh et al., 2020)
paradigm. DynaBERT (Hou et al., 2020) used distillation to transfer knowledge
from a width-adaptive network onto a depth-adaptive smaller network. CoFi (Xia
et al., 2022) explored the joint pruning between coarse and fine-grained
modules in the transformer architecture. A recent work, namely Post-Training-
Framework (PTF) (Kwon et al., 2022), was introduced to prune BERT in one-shot
for NLP tasks, however, it leverages domain-related tricks to boost
performance with a particular architecture and application. However, these
methods have limitations, including dependence on architecture (Kwon et al.,
2022; Lagunas et al., 2021; Hou et al., 2020) and expensive re-training
procedures (Lagunas et al., 2021; Sanh et al., 2020; Hou et al., 2020; Xia et
al., 2022). Focusing on the challenge of developing efficient transformers, we
overcome these shortcomings by introducing a one-shot framework that produces
competitive results at significant FLOPs reductions across several application
domains.

Compressing Vision Transformers There have been several approaches to
compressing vision transformers by focussing on different compute-intensive
modules. $\text{S}^{2}\text{ViTE}$ (Chen et al., 2021) explored structured
sparsity by modifying first-order importance approximations enabling the
dynamic sizing of attention heads in the ViT. SAViT (Chuanyang et al., 2022)
developed a collaborative pruning scheme that analyzes component interaction
to learn individual pruning ratios. Another stream of research introduced
token reduction methods to accelerate both the training and inferencing
throughput by gradually removing tokens from propagating forward in a
Transformer (Kong et al., 2022; Fayyaz et al., 2022). EViT (Liang et al.,
2022) builds on a Top-K approach by creating a fused token at each reduction
stage to minimize the information lost from pruning. DynamicViT (Rao et al.,
2021) introduced a lightweight prediction module to derive the importance
scores of each patch per input. ToMe (Bolya et al., 2023) was introduced as
one of the first one-shot methods in token reduction and leveraged bipartite
matching to merge a fixed number of tokens at each transformer block
regardless of input patches. TPS (Wei et al., 2023) furthered token reduction
and merging, by identifying a pruned subset and squeezing the informative
regions into a reserved subset of kept tokens. However, these methods still
have limitations that prevent their widescale use including architecture
specific design (Song et al., 2022; Chuanyang et al., 2022; Bolya et al.,
2023) and expensive re-training policies (Chen et al., 2021; Chuanyang et al.,
2022; Liang et al., 2022; Rao et al., 2021; Wei et al., 2023). In contrast,
the OPTIN Framework leverages a one-shot approach to compress vision
transformers across classification and semantic segmentation achieving
competitive performance amongst state-of-the-art. The granularity and number
of prunable components in the domain of vision transformers widely differ
across state-of-the-art methods (Song et al., 2022). Similarly, the OPTIN
Framework increases the base prunable components by allowing for the
incorporation of token reduction methods through generating an optimal
reduction policy as discussed in Sec. 4.2.

##  3 Measuring Trajectory

We aim to compress pre-trained transformer models by removing prunable
parameters with minimal importance scores as determined by our salience metric
without re-training. By analyzing the effects of parameter removal on deeper
layers in the network, our trajectory metric is able to better select
important parameters by leveraging long-term inter-layer dependencies in the
model.

Problem Statement. Given a model $f$ (with $N$ layers) expressed by its
collection of weights
$\left[\theta_{0},\theta_{1},\cdots\theta_{N}\right]\in\mathbb{R}^{N\times
d}$, a pruned subset has weight collection
$\left[\theta^{\prime}_{0},\theta^{\prime}_{1},\cdots\theta^{\prime}_{N}\right]\in\mathbb{R}^{N\times
d}$, such that $\theta^{\prime}=m\odot\theta$ where $m\in\\{0,1\\}^{d}$ is a
binary mask and $\odot$ is the element wise product operator. We define this
pruned subset to be optimal if it satisfies the cost constraint and results in
the minimum decrease in validation error from the base model expressed with
$\mathcal{L}_{err}$. Formally, we express this as:

$\displaystyle\text{argmin}_{\left[\theta^{\prime}_{0},\theta^{\prime}_{1},\cdots\theta^{\prime}_{N}\right]}\quad\mathcal{L}_{err}(f(X,\left[\theta_{0},\theta_{1},\cdots\theta_{N}\right]),f(X,\left[\theta^{\prime}_{0},\theta^{\prime}_{1},\cdots\theta^{\prime}_{N}\right]))$
$\displaystyle\quad\text{subject
to}\quad\mathcal{C}(\left[\theta^{\prime}_{0},\theta^{\prime}_{1},\cdots\theta^{\prime}_{N}\right])\leq
C.$ (1)

where, the optimal selection of weights
$\left[\theta^{\prime}_{0},\theta^{\prime}_{1},\cdots\theta^{\prime}_{N}\right]$
meets the cost requirement $C$ while retaining the minimum drop in validation
performance on the dataset $X$.

Approach In general, for each transformer block we define the prunable weights
as the collection of attention heads and fully connected neurons, individually
denoted by $\theta_{i,j}$ where the parameter is located in layer $i$ at an
arbitrary index $j$. The exact prunable components for each task are described
in Appendix A.8. We progressively mask each prunable parameter, and compute
the importance score by executing a forward pass that originates from layer
$i$ and propagates forward to the logit prediction. In particular we express
the masking of weight $j$ in layer $i$ as $MASK_{j}\odot\theta_{i}$ where
$MASK$ is the instance of $m$ with a single zero at location $j$, as used in
Algorithm 1. This masked forward pass yields subsequent layer-wise activations
and output logits, which are both used in computing the trajectory of
parameter, $\theta_{i,j}$. We denote the cumulative importance of parameter,
$\theta_{i,j}$, as $\mathcal{I}_{i,j}$. Referring to the optimization problem
in Eq. 1, we use our importance metric as a proxy for determining which
parameters will least affect the validation error, $\mathcal{L}_{err}$, on the
testing dataset, $X$. Upon computing all importance scores
$\mathcal{I}_{i,j}$, we employ an expedited mask-search policy, from (Kwon et
al., 2022), which computes the optimal configuration in a faster polynomial-
time by sequentially adding parameters in descending importance. Further
details on the search method are discussed in Appendix A.1. We introduce the
OPTIN Framework algorithm in Algorithm 1 and Diagram in Fig. 1.

Algorithm 1 OPTIN Framework for Model Compression

1:Inputs:  FLOPs Constraint ($\mathcal{C}$), Importance Scores
($\mathcal{I}\xleftarrow{}[]$), model, batch

2:$\left(\left[\mathcal{F}_{0},\cdots\mathcal{F}_{N}\right],logits\right)\xleftarrow{}model(batch)$
$\triangleright$ Pre-Compute Forward Pass

3:for $\theta_{i}$ in $\left[\theta_{0},\theta_{1},\cdots\theta_{n}\right]$ do
$\triangleright$ layer: $i$

4: for $j\in\texttt{range(}d\texttt{)}$ do $\triangleright$ weight: $j$

5:
$\texttt{model[}i\texttt{].weight}\xleftarrow{}\theta_{i}*MASK_{j}$$\triangleright$
$\texttt{Apply Mask to Weight }(i,j)$

6:
$\left(\left[\mathcal{F}^{\prime}_{0},\cdots\mathcal{F}^{\prime}_{N}\right],logits^{\prime}\right)\xleftarrow{}\texttt{model(batch)}$
$\triangleright$ Compute Masked Forward Pass

7:
$\mathcal{I}_{i,j}\xleftarrow[]{}\sum^{N}_{z=i+1}\mathcal{L}_{MD}(F_{z}^{{}^{\prime}},F_{z})+\lambda\mathcal{L}_{KD}$
$\triangleright$ Apply Eq.2 and 3

8: end for

9:end for

10:$\texttt{Reduced
Model}\xleftarrow{}\texttt{SEARCH}(\mathcal{I},\mathcal{C})$

Figure 1: Illustrates the computation of the OPTIN Frameworks trajectory
metric on weight $\theta_{i,j}$. By applying a mask to weight $\theta_{i,j}$
in $\texttt{Layer}_{i}$ and executing a forward pass, the OPTIN framework can
measure the effect on future layer embeddings (trajectory), as an indicator of
weight importance. $\mathcal{L}_{MD}$ is the manifold distillation loss
computed between layer embeddings at each transformer block, while
$\mathcal{L}_{KD}$ is the KL-Divergence computed between the original logits
and those due to the masked weight. The combination losses are further
detailed in the Weight Importance heading under Sec. 3

Parameter Importance Prior to assigning an importance score to each parameter,
we define what it means to be “important”. While many prior works have coined
the importance of parameters by analyzing their intrinsic structure and error
dynamics (Kurtic et al., 2022), these are not necessarily the most intuitive.
For instance, magnitude-based metrics (Li et al., 2017) capture the intrinsic
dominant property of individual weight structures, however, fail to capture
their interactions with the data, meanwhile, activation methods (Lin et al.,
2023) can capture in-place reconstruction errors, however, they may obscure
the global impact on deeper layers in the model. Motivated by capturing the
long-term effects of weights, we frame the problem as identifying which
weights are more important based on how much they affect subsequent layer
embeddings, hence we coin the measure trajectory.

Dataset |  Emb. |  Acc.
---|---|---
MNLI |  L-Norm |  81.92
MNLI |  FFN |  81.90
MNLI |  IM-Dense |  81.83
|  |
ImageNet |  L-Norm |  71.27
ImageNet |  FFN |  71.25
ImageNet |  IM-Dense |  70.90
|  |
(a)

Dataset |  Temp. |  Acc.
---|---|---
MNLI |  1 |  82.01
MNLI |  2 |  82.11
MNLI |  4 |  81.90
MNLI |  8 |  82.14
ImageNet |  1 |  70.54
ImageNet |  2 |  70.77
ImageNet |  4 |  71.25
ImageNet |  8 |  71.00
(b)

Dataset |  Aggregate |  Acc.
---|---|---
MNLI |  sum |  81.90
MNLI |  mean |  80.75
|  |
|  |
ImageNet |  sum |  71.25
ImageNet |  mean |  71.15
|  |
|  |

(c)

Dataset |  $\mathcal{L}_{MD}$ |  $\mathcal{L}_{KD}$ |  $\lambda_{c}$ |  Acc.
---|---|---|---|---
Language |  MNLI |  ✓ |  - |  - |  81.71
|  MNLI |  - |  ✓ |  - |  80.91
|  MNLI |  ✓ |  ✓ |  10 |  81.74
|  MNLI |  ✓ |  ✓ |  1 |  81.86
|  MNLI |  ✓ |  ✓ |  0.1 |  81.90
|  MNLI |  ✓ |  ✓ |  0.01 |  82.12
Vision |  ImageNet |  ✓ |  - |  - |  70.34
|  ImageNet |  - |  ✓ |  - |  68.85
|  ImageNet |  ✓ |  ✓ |  10 |  70.82
|  ImageNet |  ✓ |  ✓ |  1 |  70.85
|  ImageNet |  ✓ |  ✓ |  0.1 |  70.99
|  ImageNet |  ✓ |  ✓ |  0.01 |  71.25

(d)

Dataset |  $\text{Type}^{\dagger}$ |  Acc.
---|---|---
MNLI |  $[i]$ |  78.89
MNLI |  $[i+1]$ |  80.07
MNLI |  $[i,N]$ |  81.65
MNLI |  $[i+1,N]$ |  81.90
|  |
|  |
ImageNet |  $[i]$ |  68.91
ImageNet |  $[i+1]$ |  69.55
ImageNet |  $[i,N]$ |  70.04
ImageNet |  $[i+1,N]$ |  71.25
|  |
|  |
(e)

Table 1: Ablative Experiments on Trajectory using $\texttt{BERT}_{BASE}$
(Kenton & Toutanova, 2019) on the GLUE benchmark MNLI dataset (Wang et al.,
2019), and DeiT-Ti (Touvron et al., 2021) on the ImageNet-1K dataset (Deng et
al., 2009) to explore the effect parameters on model performance. We measure
one-shot post-pruning accuracies over various configurations on both the
language and vision datasets. In particular (a) explores locations to extract
features for distillation loss: L-Norm (After Layer Normalization), FFN (After
Dense output layer), IM-Dense(After Dense Embedding Layer). (b) examines the
effect of temperature in the KL-Divergence Formulation, (c) explores the
effect of summing or averaging over the layer distillation error, (d) explores
the effect of metrics $\mathcal{L}_{MD}$ and $\mathcal{L}_{KD}$ as well as
their balancing paramter $\lambda$, (e) explores which layer to accumulate the
distillation error in relation current layer $i$. Compression rates remain
consistent with Tab. 8 and Tab 3. The baseline performance of
$\texttt{BERT}_{BASE}$ on MNLI is 84.53%, meanwhile DeiT-Ti on ImageNet-1K is
$\textbf{72.20\%}\%$. Our default settings are marked in green.

Effect on Trajectory To compute the trajectory of a weight, $\theta_{i,j}$ we
follow a 2-step procedure. Firstly, we measure layer-wise activation errors
prior to the LayerNorm operator at each block subsequent to the layer of
interest. We conducted an ablative study in
LABEL:tab:ablation_embedding_choice showing the effect of using pre-layer norm
embeddings. We first define the feature output of layer $i$ as
$\mathcal{F}_{i}\in\mathbf{R}^{B\times T\times D}$, where $B$ is the batch
size, $T$ is the token length and $D$ is the embedding dimension. We similarly
express the feature output of the masked network using the
$\texttt{prime}^{\prime}$ symbol. Inspired by distillations works (Sajedi et
al., 2023a; Peng et al., 2019), we compute the layer-wise error by adopting
fine-grained manifold distillation (Hao et al., 2022). A reshaping operator
$\psi(\cdot)\in\mathbf{R}^{BT\times D}$ leverages patch and batch level
information, defining the relational map and associated metric as:

$\displaystyle\mathcal{M}(F_{i})$ $\displaystyle=\psi(F_{i})\psi(F_{i})^{T}$
$\displaystyle\mathcal{L}_{MD}(F_{i}^{{}^{\prime}},F_{i})=||\mathcal{M}(F_{i}^{{}^{\prime}})-\mathcal{M}(F_{i})||^{2}_{F}$
(2)

However, unlike previous works, we do not use this loss to guide training or
distillation, rather, we express it as an in-place metric to help understand
parameter importance throughout the network.

If the masked weight is at position $j$ in layer $i$, the computed error is
accumulated over both the dimension $D$ and at each layer $l$ in the range
$\left[i+1,N\right]$. The choice of error aggregation was explored in Tab.
LABEL:tab:ablation_head_aggregation and clearly demonstrated the benefit of
the sum operator. Additionally, we explored the effect of modifying which
layers were relevant to the trajectory – see Tab. LABEL:tab:trajectoryDepth –
overall it was evident that using subsequent layers yielded the best result,
correctly aligning with the original motivation.

Effect on Logits Next we compute the effects on the logit prediction as shown
in Fig. 1 with $\mathcal{L}_{KD}$. Several works have shown the effects of
using logit predictions to guide the training process with distillation (Hao
et al., 2022; Zhao et al., 2022) or correlation (Sajedi et al., 2024; 2023b).
However, in this work, we use the $\mathcal{L}_{KD}$ loss (defined in (Hinton
et al., 2015)) as an in-place metric to quantify the importance of a
particular weight. We ablate the temperature value in Tab.
LABEL:tab:ablation_temperature. Thus, if masking a particular weight produces
a larger $\mathcal{L}_{KD}$, we would hypothesize that it is a more important
weight.

We can formalize the importance of a particular weight $j$ at layer $i$ with
iterator $z$ as:

$\displaystyle\mathcal{I}_{i,j}=\sum^{N}_{z=i+1}\mathcal{L}_{MD}(F_{z}^{{}^{\prime}},F_{z})+\lambda\mathcal{L}_{KD}$
(3)

where $\mathcal{I}_{i,j}$ is defined for a particular weight in a particular
layer, $\lambda$ controls the contribution effect of KD, and
$\mathcal{L}_{MD}$ compares the pruned and original resulting embeddings in
deeper layers. We ablate the effect of different $\lambda$ values as well as
the contribution of each loss individually in Tab.
LABEL:tab:ablation_component. Further, we show that applying a greater
importance on $\mathcal{L}_{MD}$ results in better parameter selection.
Further details on the contribution hyperparameter are expressed in Appendix
A.2.

We also provide the algorithm for applying OPTIN on a generic model instance
in Algorithm 1.

##  4 Experimental Design

In this section, we demonstrate the effectiveness of the OPTIN Framework, at
improving model performance and throughput given strict FLOP reduction ratios.
We introduce implementation and evaluation details to ensure reproducibility
and benchmark our method with state of art in natural language and image
classification to illustrate the potential of our one-shot framework. We
further investigate the applications in transfer learning, alternate
architectures, and downstream tasks to show the generalizability of our method
across tasks and architectures.

Experimental Setup We implement our method using transformers from the
HuggingFace Library (Wolf et al., 2020) and infrastructure from PyTorch
(Paszke et al., 2019). The majority of our experiments explore using the OPTIN
Framework to improve off-the-shelf models without re-training. The exceptions
include select experiments in the Applications Section, see Sec. 4.3. The
OPTIN Framework computes parameter importance on the basis of training data in
a gradient-free forward pass. The amount (batch) of data used to compute the
scores is ablated in Appendix A.6. Finally, details on the prunable components
under each setting are described in Appendix A.8.

Datasets & Networks The OPTIN Framework is tested against a variety of network
architectures and datasets to ensure generalizability over both the task and
model domains. For Natural Language Processing, OPTIN is evaluated on the GLUE
Benchmark (Wang et al., 2019) using the $\text{BERT}_{BASE}$ (Kenton &
Toutanova, 2019) architecture. For Image Classification, both ImageNet1-K
(Deng et al., 2009) and CIFAR10 (Krizhevsky et al., 2009) were used with the
DeiT-Ti/S/B (Touvron et al., 2021), ViT-B (Dosovitskiy et al., 2021), and a
VGGNet (Simonyan & Zisserman, 2014)

architecture to demonstrate the OPTIN Framework’s robustness on model
type/size, image datasets, and transfer learning. For Semantic Segmentation,
the Cityscapes Dataset (Cordts et al., 2016) was used with the Mask2Former
(Cheng et al., 2022) with a Swin-Ti backbone (Liu et al., 2021a) to show how
the OPTIN Framework could be used to maintain competitive performance and
throughput at constrained FLOPs. Further details on dataset selection are in
Appendix A.3

Evaluation Metrics With the goal of model compression, we evaluate models
based on their accuracy (or mIoU for segmentation) given a FLOP reduction.
Details regarding the metric choice for the corresponding task can be found in
Appendix A.4. In select cases, we include latency measurments expressed as a
ratio of the improved inferencing speed to that of the baseline. All time
measurements are captured over 300 iterations on an Nvidia RTX 2080 using a
100-iteration warmup.

###  4.1 Language Experiments

Performance on NLP Benchmarks In Tab. 8 we investigate the OPTIN Framework for
compressing language models on the GLUE dataset using $BERT_{BASE}$. Measuring
performance and throughput speeds, we show a relatively low average decline in
baseline accuracy ($\leq 2\%$) at a $40\%$ FLOPS compression rate. Similarly,
we benchmark our performance with a leading one-shot SoTA method: Post-
Training-Pruning-Framework (PTF)(Kwon et al., 2022) at the same compression
rate and show superior performance. In particular, we compare with the mask
search results from PTF, as subsequent phases in their method could be stacked
on other post-training pruning methods (refer to Appendix A.7 for exetended
comparisons). We demonstrate robustness over various compression ratios in
Fig. 3 where we benchmark OPTIN against pipelines that incorporate re-
training, including CoFi (Xia et al., 2022), DynaBert(Hou et al., 2020), SLIP
(Lin et al., 2020b), EBERT(Liu et al., 2021b), BMP (Lagunas et al., 2021) and
FLOP (Wang et al., 2020b). Despite the added re-training phase in other
methods, the OPTIN Framework is able to retain competitive test performance
over a variety of compression ratios thus establishing a compelling argument
for retraining-free pipelines.

Method |  MNLI |  QQP |  QNLI |  SST |  STS-B |  MRPC
---|---|---|---|---|---|---
$\text{BERT}_{BASE}$ |  84.53 |  91.00 |  91.41 |  93.57 |  88.90 |  86.27
$\text{PTF}^{\dagger}$ |  81.21 |  89.99 |  88.38 |  92.13 |  87.10 |  83.14
$\textbf{OPTIN}^{\ddagger}$ |  81.90 |  90.06 |  88.49 |  92.24 |  87.25 |  85.13

Table 2: Natural Language Benchmarks. Comparing OPTIN performance on the GLUE
(Wang et al., 2019) benchmark (refer to A.7 for additional results). The
relative FLOP constraint is set to 60% for a fair comparison.

Figure 3: Natural Language FLOPs vs Accuracy. We directly benchmark the OPTIN
Framework against leading state-of-the-art methods in natural language model
compression. Due to the numerous different baselines reported in each work, we
plot the relative performance drops for each method. On the right, we compare
the performance gap with latency showing that with an average drop of $\leq
1.75\%$ we can achieve a $1.25\times$ speedup in throughput purely from static
model size reduction.

###  4.2 Vision Experiments

Extending to Image Classification Transitioning the OPTIN Framework from the
language domain to the vision domain, we were required to increase the number
of prunable components. Comparable works have used a larger number of
components including the pruning of Q-K-V layers in each attention head,
tokens & patches, and final embeddings in each transformer block (Zhu et al.,
2021; Wei et al., 2023; Pan et al., 2021). Thus the state of the art in the
field of transformer pruning widely differs in the granularity and consistency
of the pruned components. With a priority on reducing real-world inference
time, we extend OPTIN to include a variant of token reduction; a similar
adaptation was made in CP-ViT (Song et al., 2022). In particular, we derive a
modified trajectory formulation to rank tokens between each transformer block
as described in Appendix A.9. By incorporating the trajectory metric for
layerwise-token ranking, the OPTIN framework can deduce the optimal number of
tokens to preserve between each transformer block, and can thus create an
informative token reduction schedule that can be leveraged by any token
reduction method. In particular, we were inspired by a recent work, ToMe
(Bolya et al., 2023) which features an efficient token merging technique based
on bipartite matching that removes tokens between transformer blocks either at
a constant or linearly decreasing schedule. We incorporate ToMe as a method of
merging tokens based on the optimal number of reduced tokens per layer
determined by the OPTIN framework search. Since our framework produces the
reduction schedule, we can leverage the benefit of batching as the number of
tokens per image will be constant, and the methods of merging or reducing can
be selected by any user – we ablate the bipartite matching scheme with a
random pruning scheme in Appendix A.6 and show similar improvements when using
the OPTIN Framework.

Method |  DeiT Tiny |  DeiT Small
---|---|---
|  FLOPs(G) |  Acc(%) |  FLOPs(G) |  Acc(%)
Baseline |  1.3 |  72.2 |  4.6 |  79.8
Re-Trained
SSP |  $0.99^{{\color[rgb]{1,0,0}\downarrow 23.7\%}}$ |  68.59 |  $3.15^{{\color[rgb]{1,0,0}\downarrow 31.6\%}}$ |  77.74
$S^{2}$ViTE |  $0.99^{{\color[rgb]{1,0,0}\downarrow 23.7\%}}$ |  70.12 |  $3.15^{{\color[rgb]{1,0,0}\downarrow 31.6\%}}$ |  79.22
$\text{SAViT}^{\dagger\dagger}$ |  $0.98^{{\color[rgb]{1,0,0}\downarrow 24.4\%}}$ |  70.72 |  - |  -
Not Re-Trained
$\text{VTP}^{\dagger}$ |  $1.00^{{\color[rgb]{1,0,0}\downarrow 21.7\%}}$ |  69.37 |  $3.65^{{\color[rgb]{1,0,0}\downarrow 20.7\%}}$ |  77.35
$\text{PoWER}^{\dagger}$ |  $1.02^{{\color[rgb]{1,0,0}\downarrow 20.3\%}}$ |  69.56 |  $3.61^{{\color[rgb]{1,0,0}\downarrow 21.5\%}}$ |  77.02
$\text{HVT}^{\dagger}$ |  $1.01^{{\color[rgb]{1,0,0}\downarrow 21.2\%}}$ |  68.43 |  $3.66^{{\color[rgb]{1,0,0}\downarrow 20.5\%}}$ |  76.72
$\text{CP-ViT}^{\dagger}$ |  $1.00^{{\color[rgb]{1,0,0}\downarrow 23.0\%}}$ |  71.06 |  $3.64^{{\color[rgb]{1,0,0}\downarrow 21.0\%}}$ |  78.84
$\textbf{OPTIN}_{\beta}$ |  $1.1^{{\color[rgb]{1,0,0}\downarrow 15.46\%}}$ |  67.51 |  $4.11^{{\color[rgb]{1,0,0}\downarrow 11.2\%}}$ |  77.01
$\textbf{OPTIN}_{\tau}$ |  $0.91^{{\color[rgb]{1,0,0}\downarrow 29.7\%}}$ |  71.25 |  $3.15^{{\color[rgb]{1,0,0}\downarrow 31.6\%}}$ |  79.24

Table 3: Pruning ImageNet-1K. Benchmarking the performance of OPTIN using
DeiT-Tiny/Small. † methods are reproduced in (Song et al., 2022) without re-
training. †† DeiT-S result from (Chuanyang et al., 2022) is excluded as it
performs superior to the available baseline. OPTIN framework runs without re-
training producing both the $\beta$ and $\tau$ configurations.

Figure 4: DeiT-Ti FLOPs vs Accuracy Benchmarking $\texttt{OPTIN}_{\tau}$ over
a range of FLOP reductions on ImageNet-1K. OPTIN shows strong robustness over
various FLOP constraints without re-training.

Model | Method |  ImageNet-1K |  Transfer$\xrightarrow{}$C-10
---|---|---|---
|  | FLOPs(G) | Acc(%) | FLOPs(G) | Acc(%)
DeiT-S |  Baseline |  4.6 |  79.8 |  4.6 |  97.13
|  $\textbf{OPTIN}_{\tau}$ |  $3.52^{{\color[rgb]{1,0,0}\downarrow\textbf{23.7}\%}}$ |  79.01 |  $2.30^{{\color[rgb]{1,0,0}\downarrow\textbf{50.0}\%}}$ |  96.60
ViT-B |  Baseline |  17.47 |  75.40 |  17.47 |  98.01
|  $\textbf{OPTIN}_{\tau}$ |  $13.33^{{\color[rgb]{1,0,0}\downarrow\textbf{23.7}\%}}$ |  72.98 |  $8.77^{{\color[rgb]{1,0,0}\downarrow\textbf{50.0}\%}}$ |  97.82

Table 4: Transfer Learning on CIFAR Dataset. Benchmarking the performance of
OPTIN on the CIFAR-10 Datasets. Models were pre-trained on ImageNet-1K, pruned
through the OPTIN Framework $\tau$ configuration, and transferred learned at a
more aggressive pruning rate onto the CIFAR-10 (C-10) Dataset.

Method | FLOPs(G) | $\pm\triangle$Acc($\%$)
---|---|---
ViT-B |  17.47 |  –
ToMe |  11.50 |  $\downarrow$ 1.88
$\textbf{OPTIN}_{\tau(\infty)}$ |  11.45 |  $\downarrow$ 0.71
DeiT-B |  17.6 |  –
Dyn-ViT† |  11.81 |  $\downarrow$ 1.17
Top-K† |  11.81 |  $\downarrow$ 0.94
EViT† |  11.81 |  $\downarrow$ 0.86
ToMe† |  11.81 |  $\downarrow$ 0.80
TPS†† |  11.51 |  $\downarrow$ 0.71
$\textbf{OPTIN}_{\tau(\infty)}$ |  11.75 |  $\downarrow$ 0.52

Table 5: Token Reduction Benchmarking $\texttt{OPTIN}_{\tau(\infty)}$
configuration. ${}^{\dagger}\&^{\dagger\dagger}$ detailed in the main text.

Image Classification Results In Tab. 3 we benchmark our proposed re-training
free method on the ImageNet-1K dataset with the baseline, and SOTA results to
show competitive performance at given FLOPs reductions. We offer two
configurations: $\beta$ (base) denotes the base OPTIN Framework without the
additional prunable components (directly shifted from the language domain),
$\tau$ (expanded) denotes the incorporation of token reduction into our search
space. Compared with methods that perform re-training, the OPTIN Framework
produces competitive performance, particularly with a $0.5\%$improvement at a
$5\%$ lower FLOPs with respect to SAViT(Chuanyang et al., 2022). Comparing
with methods that have removed re-training, we note that VTP (Zhu et al.,
2021) still includes additional sparsity-regularization training, PoWER (Goyal
et al., 2020) still includes the auxiliary network training with soft-extract,
and HVT (Pan et al., 2021) still reduces FLOPs via re-training the
architecture with a pooling method. However our method is considered a
fundamentally one-shot design and despite lacking these additional pruning
artifacts & components, is still able to outperform the current SoTA, with the
best result on DeiT-Small outperforming CP-ViT(Song et al., 2022) by $0.4\%$
at a $\sim 10\%$ higher FLOPs reduction. To further benchmark our performance
in perspective of a wider FLOPs spectrum and more model compression methods,
we introduce Fig 4 which includes: X-Pruner (Yu & Xiang, 2023), WDPruning (Yu
et al., 2022a), S2VITE/SSP(Chen et al., 2021), SCOP (Tang et al., 2020), HVT
(Pan et al., 2021), SAViT(Chuanyang et al., 2022), VTP (Zhu et al., 2021),
PoWER(Goyal et al., 2020), CP-ViT(Song et al., 2022) and UVC (Yu et al.,
2022b). Despite our lack of re-training, the OPTIN framework produces
competitive results over various flop ratios.

For completeness, we chose to introduce a third configuration
$\tau_{(\infty)}$ which only applies OPTIN to creating token reduction
schedule, while leveraging ToMe for merging. Under this constraint, we
evaluate our method with state-of-the-art token reduction methods: including
DynamicViT (Dyn-ViT) (Rao et al., 2021), Top-K (Haurum et al., 2023), EViT
(Liang et al., 2022) and TPS (Wei et al., 2023) in Tab 5 and show superior
performance under our framework without re-training. $\dagger$ methods follow
setup & produced results in (Haurum et al., 2023), we convert a token
percentage to FLOPs reduction to benchmark our method.$\dagger\dagger$
estimated from (Wei et al., 2023). We further complement this with a more
detailed comparison against the schedules using constant and linearly
decreasing reduction schedules in ToMe over a wide variety of FLOP constraints
in Appendix A.6. Ultimately this provides a compelling case for OPTIN’s
ability to effectively determine average token importance in transformer
architectures.

Transfer-Learning for Image Classification To demonstrate the transferability
of our compressed models, we obtain the pruned networks from ImageNet-1K and
apply transfer learning to the CIFAR-10 dataset. We choose to include DeiT-S
and ViT-B for model size diversity. Benchmarking against baseline models, in
Tab 4 we show significant recovery of performance when transferring learning
onto CIFAR-10 at extensive FLOPs reduction ratios. Although we show re-
training is not necessary when it comes to pruning on a specific dataset &
task, we evidently show that the method works well under the transfer learning
paradigm for different downstream purposes.

###  4.3 Applications

We explore downstream tasks and architectures that can similarly benefit from
the OPTIN Framework. Particularly, high-resolution (HR) semantic segmentation
is a compute-intensive task, and we explore how OPTIN maintains competitive
performance and increases throughput speeds in Tab
LABEL:fig:seg_pruning_comparison and Fig LABEL:fig:high_res_seg. To show
generalizability, we include a small experiment on CNN pruning in 6.

Method |  FLOPs(M) |  Top-1(%) |  Epochs
---|---|---|---
Baseline |  313.73 |  93.96 |  -
$L^{1}$ |  206.00 |  93.40 |  -
HRank |  131.17 |  93.73 |  200-300
CFDP |  131.17 |  94.10 |  200-300
OPTIN |  131.17 |  94.10 |  100-150

Table 6:  Pruning on CNN. Benchmarking the performance of OPTIN on the
CIFAR-10(Krizhevsky et al., 2009) dataset using VGG-16-BN. OPTIN outperforms
previous model compression techniques.

Method |  FLOPs$\downarrow$ |  Params$\downarrow$ |  mIoU(%) |  Latency($\downarrow$)
---|---|---|---|---
Baseline |  - |  - |  78.81 |  -
$\textbf{OPTIN}_{\beta}$ |  24.2% |  46.6% |  74.57 |  13%

(a)

(b)

Figure 5: Evaluated $\texttt{OPTIN}_{\beta}$ on HR (1024x2048) Segmentation
((a) Quantitative; (b) Qualitative).

Exploring Semantic Segmentaion To demonstrate the OPTIN framework’s
generalizability to complex architectures and downstream tasks, we apply model
compression to the Mask2Former Architecture with the Swin-Tiny backbone on the
Cityscapes dataset. We specify the selected prunable components in Appendix
A.8. In Tab. LABEL:tab:seg_pruning_comparison we show impressive performance
despite roughly a $24\%$ reduction in FLOPs and $47\%$ reduction in parameters
of the endocer. Qualitatively we can see a strong resemblance between the
original and compressed network, with a small discrepancy in predictions
towards the bottom right of the frame in an already difficult-to-segment
region (as evidenced by the unclear segmentation in the original prediction)
and on the traffic sign towards the top left in Fig. LABEL:fig:high_res_seg.

Exploring CNN Architectures To demonstrate the potential applications of OPTIN
onto CNN architectures, we extend our trajectory measure as described in
Appendix A.10. In Tab. LABEL:tab:seg_pruning_comparison we compare the model
compressed through the OPTIN Framework with the baseline on the VGG-16-BN
architecture, a heuristic approach ($\mathcal{L}^{1}$) (Li et al., 2017) and
two leading state-of-ther-art: HRank (Lin et al., 2020a) and CFDP(Khaki & Luo,
2023). Following previous works (Lin et al., 2020a), fine-tuning has been
shown to be required post-compression. However as evident in Tab
LABEL:tab:seg_pruning_comparison, following the same training procedures as
HRank, we were able to outperform all methods at a much faster convergence
speed given comparable FLOPs reductions.

##  5 Conclusion

In this work, we introduced OPTIN as a one-shot technique to enable efficient
compression of modern pre-trained transformer architectures without re-
training. OPTIN exploits the trajectory of prunable components in the
transformer architecture to enable a smarter criterion for parameter
selection. In this work, we’ve explored several domains including natural
language processing, image classification, transfer learning and semantic
segmentation tasks. We additionally show how our method can work in concert
with existing token reduction modules to produce even stronger competitive
results in the image domain. We further expanded our method to show robustness
on prior CNN-style architectures opening future avenues of research into fused
architectures. In all cases, we’ve shown robustness against compression rates
and competitive performance including against methods that perform re-
training. We complement our performance improvements with synonymous
improvements in throughput speed enabling the practical use of our framework.
In the future, we plan to explore more complex architectures and tasks in
addition to expanding the number of prunable components to further the cause
in an efficient design of transformer models.

##  6 Reproducibility Statement

The attached supplemental code contains a framework with the algorithms and
metrics behind our main results. All of our adapted $\mathcal{L}$ formulations
are described in the main paper: Sec 3 or Appendix A.9, A.10, and are
implemented in the supplemental code. By our innate one-shot structure, there
are no training augmentations applied as we don’t re-train. The exception is
for transfer learning and re-training on the CNN architectures. For these, we
adopt the standard augmentations from HRank (Lin et al., 2020a). Our datasets
and evaluation metrics are described in Appendix A.3, A.4.

## References

  * Bolya et al. (2023) Daniel Bolya, Cheng-Yang Fu, Xiaoliang Dai, Peizhao Zhang, Christoph Feichtenhofer, and Judy Hoffman.  Token merging: Your vit but faster.  In _The Eleventh International Conference on Learning Representations_ , 2023.  URL https://openreview.net/forum?id=JroZRaRw7Eu.
  * Chen et al. (2021) Tianlong Chen, Yu Cheng, Zhe Gan, Lu Yuan, Lei Zhang, and Zhangyang Wang.  Chasing sparsity in vision transformers: An end-to-end exploration.  _Advances in Neural Information Processing Systems_ , 34:19974–19988, 2021.
  * Cheng et al. (2022) Bowen Cheng, Ishan Misra, Alexander G Schwing, Alexander Kirillov, and Rohit Girdhar.  Masked-attention mask transformer for universal image segmentation.  In _Proceedings of the IEEE/CVF conference on computer vision and pattern recognition_ , pp. 1290–1299, 2022.
  * Chuanyang et al. (2022) Zheng Chuanyang, Zheyang Li, Kai Zhang, Zhi Yang, Wenming Tan, Jun Xiao, Ye Ren, and Shiliang Pu.  SAVit: Structure-aware vision transformer pruning via collaborative optimization.  In Alice H. Oh, Alekh Agarwal, Danielle Belgrave, and Kyunghyun Cho (eds.), _Advances in Neural Information Processing Systems_ , 2022.  URL https://openreview.net/forum?id=w5DacXWzQ-Q.
  * Cordts et al. (2016) Marius Cordts, Mohamed Omran, Sebastian Ramos, Timo Rehfeld, Markus Enzweiler, Rodrigo Benenson, Uwe Franke, Stefan Roth, and Bernt Schiele.  The cityscapes dataset for semantic urban scene understanding.  In _Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR)_ , June 2016.
  * Deng et al. (2009) Jia Deng, Wei Dong, Richard Socher, Li-Jia Li, Kai Li, and Li Fei-Fei.  Imagenet: A large-scale hierarchical image database.  In _2009 IEEE conference on computer vision and pattern recognition_ , pp. 248–255. Ieee, 2009.
  * Dosovitskiy et al. (2021) Alexey Dosovitskiy, Lucas Beyer, Alexander Kolesnikov, Dirk Weissenborn, Xiaohua Zhai, Thomas Unterthiner, Mostafa Dehghani, Matthias Minderer, Georg Heigold, Sylvain Gelly, Jakob Uszkoreit, and Neil Houlsby.  An image is worth 16x16 words: Transformers for image recognition at scale.  In _International Conference on Learning Representations_ , 2021.  URL https://openreview.net/forum?id=YicbFdNTTy.
  * Fang et al. (2023) Gongfan Fang, Xinyin Ma, Mingli Song, Michael Bi Mi, and Xinchao Wang.  Depgraph: Towards any structural pruning.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , pp. 16091–16101, 2023.
  * Fayyaz et al. (2022) Mohsen Fayyaz, Soroush Abbasi Koohpayegani, Farnoush Rezaei Jafari, Sunando Sengupta, Hamid Reza Vaezi Joze, Eric Sommerlade, Hamed Pirsiavash, and Juergen Gall.  Adaptive token sampling for efficient vision transformers.  In _European Conference on Computer Vision (ECCV)_ , 2022.
  * Goyal et al. (2020) Saurabh Goyal, Anamitra Roy Choudhury, Saurabh Raje, Venkatesan Chakaravarthy, Yogish Sabharwal, and Ashish Verma.  Power-bert: Accelerating bert inference via progressive word-vector elimination.  In _International Conference on Machine Learning_ , pp. 3690–3699. PMLR, 2020.
  * Hao et al. (2022) Zhiwei Hao, Jianyuan Guo, Ding Jia, Kai Han, Yehui Tang, Chao Zhang, Han Hu, and Yunhe Wang.  Learning efficient vision transformers via fine-grained manifold distillation.  In _Advances in Neural Information Processing Systems_ , 2022.
  * Haurum et al. (2023) Joakim Bruslund Haurum, Sergio Escalera, Graham W. Taylor, and Thomas B. Moeslund.  Which tokens to use? investigating token reduction in vision transformers.  In _Proceedings of the IEEE/CVF International Conference on Computer Vision (ICCV) Workshops_ , October 2023.
  * Hinton et al. (2015) Geoffrey Hinton, Oriol Vinyals, and Jeff Dean.  Distilling the knowledge in a neural network, 2015.
  * Hou et al. (2020) Lu Hou, Zhiqi Huang, Lifeng Shang, Xin Jiang, Xiao Chen, and Qun Liu.  Dynabert: Dynamic bert with adaptive width and depth.  In H. Larochelle, M. Ranzato, R. Hadsell, M.F. Balcan, and H. Lin (eds.), _Advances in Neural Information Processing Systems_ , volume 33, pp. 9782–9793. Curran Associates, Inc., 2020.  URL https://proceedings.neurips.cc/paper_files/paper/2020/file/6f5216f8d89b086c18298e043bfe48ed-Paper.pdf.
  * Kenton & Toutanova (2019) Jacob Devlin Ming-Wei Chang Kenton and Lee Kristina Toutanova.  Bert: Pre-training of deep bidirectional transformers for language understanding.  In _Proceedings of naacL-HLT_ , volume 1, pp. 2, 2019.
  * Khaki & Luo (2023) Samir Khaki and Weihan Luo.  Cfdp: Common frequency domain pruning.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR) Workshops_ , pp. 4714–4723, June 2023.
  * Kim et al. (2021) Sehoon Kim, Amir Gholami, Zhewei Yao, Michael W Mahoney, and Kurt Keutzer.  I-bert: Integer-only bert quantization.  In _International conference on machine learning_ , pp. 5506–5518. PMLR, 2021.
  * Kong et al. (2022) Zhenglun Kong, Peiyan Dong, Xiaolong Ma, Xin Meng, Wei Niu, Mengshu Sun, Xuan Shen, Geng Yuan, Bin Ren, Hao Tang, et al.  Spvit: Enabling faster vision transformers via latency-aware soft token pruning.  In _Computer Vision–ECCV 2022: 17th European Conference, Tel Aviv, Israel, October 23–27, 2022, Proceedings, Part XI_ , pp. 620–640. Springer, 2022.
  * Krizhevsky et al. (2009) Alex Krizhevsky, Geoffrey Hinton, et al.  Learning multiple layers of features from tiny images.  2009\.
  * Kurtic et al. (2022) Eldar Kurtic, Daniel Campos, Tuan Nguyen, Elias Frantar, Mark Kurtz, Benjamin Fineran, Michael Goin, and Dan Alistarh.  The optimal BERT surgeon: Scalable and accurate second-order pruning for large language models.  In _Proceedings of the 2022 Conference on Empirical Methods in Natural Language Processing_ , pp. 4163–4181, Abu Dhabi, United Arab Emirates, December 2022. Association for Computational Linguistics.  doi: 10.18653/v1/2022.emnlp-main.279.  URL https://aclanthology.org/2022.emnlp-main.279.
  * Kwon et al. (2022) Woosuk Kwon, Sehoon Kim, Michael W. Mahoney, Joseph Hassoun, Kurt Keutzer, and Amir Gholami.  A fast post-training pruning framework for transformers.  In Alice H. Oh, Alekh Agarwal, Danielle Belgrave, and Kyunghyun Cho (eds.), _Advances in Neural Information Processing Systems_ , 2022.  URL https://openreview.net/forum?id=0GRBKLBjJE.
  * Lagunas et al. (2021) François Lagunas, Ella Charlaix, Victor Sanh, and Alexander Rush.  Block pruning for faster transformers.  In _Proceedings of the 2021 Conference on Empirical Methods in Natural Language Processing_ , pp. 10619–10629, Online and Punta Cana, Dominican Republic, November 2021. Association for Computational Linguistics.  doi: 10.18653/v1/2021.emnlp-main.829.  URL https://aclanthology.org/2021.emnlp-main.829.
  * Li et al. (2017) Hao Li, Asim Kadav, Igor Durdanovic, Hanan Samet, and Hans Peter Graf.  Pruning filters for efficient convnets.  In _International Conference on Learning Representations_ , 2017.  URL https://openreview.net/forum?id=rJqFGTslg.
  * Liang et al. (2022) Youwei Liang, Chongjian GE, Zhan Tong, Yibing Song, Jue Wang, and Pengtao Xie.  EVit: Expediting vision transformers via token reorganizations.  In _International Conference on Learning Representations_ , 2022.  URL https://openreview.net/forum?id=BjyvwnXXVn_.
  * Lin et al. (2023) Ji Lin, Jiaming Tang, Haotian Tang, Shang Yang, Xingyu Dang, and Song Han.  Awq: Activation-aware weight quantization for llm compression and acceleration.  _arXiv_ , 2023.
  * Lin et al. (2020a) Mingbao Lin, Rongrong Ji, Yan Wang, Yichen Zhang, Baochang Zhang, Yonghong Tian, and Ling Shao.  Hrank: Filter pruning using high-rank feature map.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR)_ , pp. 1529–1538, 2020a.
  * Lin et al. (2020b) Zi Lin, Jeremiah Liu, Zi Yang, Nan Hua, and Dan Roth.  Pruning redundant mappings in transformer models via spectral-normalized identity prior.  In _Findings of the Association for Computational Linguistics: EMNLP 2020_ , pp. 719–730, Online, November 2020b. Association for Computational Linguistics.  doi: 10.18653/v1/2020.findings-emnlp.64.  URL https://aclanthology.org/2020.findings-emnlp.64.
  * Liu et al. (2021a) Ze Liu, Yutong Lin, Yue Cao, Han Hu, Yixuan Wei, Zheng Zhang, Stephen Lin, and Baining Guo.  Swin transformer: Hierarchical vision transformer using shifted windows.  In _Proceedings of the IEEE/CVF international conference on computer vision_ , pp. 10012–10022, 2021a.
  * Liu et al. (2021b) Zejian Liu, Fanrong Li, Gang Li, and Jian Cheng.  EBERT: Efficient BERT inference with dynamic structured pruning.  In _Findings of the Association for Computational Linguistics: ACL-IJCNLP 2021_ , pp. 4814–4823, Online, August 2021b. Association for Computational Linguistics.  doi: 10.18653/v1/2021.findings-acl.425.  URL https://aclanthology.org/2021.findings-acl.425.
  * Ma et al. (2023) Xinyin Ma, Gongfan Fang, and Xinchao Wang.  Llm-pruner: On the structural pruning of large language models.  In _Advances in Neural Information Processing Systems_ , 2023.
  * Michel et al. (2019) Paul Michel, Omer Levy, and Graham Neubig.  Are sixteen heads really better than one?  _Advances in neural information processing systems_ , 32, 2019.
  * Pan et al. (2021) Zizheng Pan, Bohan Zhuang, Jing Liu, Haoyu He, and Jianfei Cai.  Scalable vision transformers with hierarchical pooling.  In _Proceedings of the IEEE/cvf international conference on computer vision_ , pp. 377–386, 2021.
  * Paszke et al. (2019) Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, Alban Desmaison, Andreas Kopf, Edward Yang, Zachary DeVito, Martin Raison, Alykhan Tejani, Sasank Chilamkurthy, Benoit Steiner, Lu Fang, Junjie Bai, and Soumith Chintala.  Pytorch: An imperative style, high-performance deep learning library.  In H. Wallach, H. Larochelle, A. Beygelzimer, F. d'Alché-Buc, E. Fox, and R. Garnett (eds.), _Advances in Neural Information Processing Systems_ , volume 32. Curran Associates, Inc., 2019.  URL https://proceedings.neurips.cc/paper_files/paper/2019/file/bdbca288fee7f92f2bfa9f7012727740-Paper.pdf.
  * Peng et al. (2019) Baoyun Peng, Xiao Jin, Jiaheng Liu, Dongsheng Li, Yichao Wu, Yu Liu, Shunfeng Zhou, and Zhaoning Zhang.  Correlation congruence for knowledge distillation.  In _Proceedings of the IEEE/CVF International Conference on Computer Vision_ , pp. 5007–5016, 2019.
  * Rao et al. (2021) Yongming Rao, Wenliang Zhao, Benlin Liu, Jiwen Lu, Jie Zhou, and Cho-Jui Hsieh.  Dynamicvit: Efficient vision transformers with dynamic token sparsification.  In A. Beygelzimer, Y. Dauphin, P. Liang, and J. Wortman Vaughan (eds.), _Advances in Neural Information Processing Systems_ , 2021.  URL https://openreview.net/forum?id=jB0Nlbwlybm.
  * Sajedi et al. (2023a) Ahmad Sajedi, Samir Khaki, Ehsan Amjadian, Lucy Z Liu, Yuri A Lawryshyn, and Konstantinos N Plataniotis.  Datadam: Efficient dataset distillation with attention matching.  In _Proceedings of the IEEE/CVF International Conference on Computer Vision_ , pp. 17097–17107, 2023a.
  * Sajedi et al. (2023b) Ahmad Sajedi, Samir Khaki, Konstantinos N Plataniotis, and Mahdi S Hosseini.  End-to-end supervised multilabel contrastive learning.  _arXiv preprint arXiv:2307.03967_ , 2023b.
  * Sajedi et al. (2024) Ahmad Sajedi, Samir Khaki, Yuri A Lawryshyn, and Konstantinos N Plataniotis.  Probmcl: Simple probabilistic contrastive learning for multi-label visual classification.  _arXiv preprint arXiv:2401.01448_ , 2024.
  * Sanh et al. (2020) Victor Sanh, Thomas Wolf, and Alexander Rush.  Movement pruning: Adaptive sparsity by fine-tuning.  In H. Larochelle, M. Ranzato, R. Hadsell, M.F. Balcan, and H. Lin (eds.), _Advances in Neural Information Processing Systems_ , volume 33, pp. 20378–20389. Curran Associates, Inc., 2020.  URL https://proceedings.neurips.cc/paper_files/paper/2020/file/eae15aabaa768ae4a5993a8a4f4fa6e4-Paper.pdf.
  * Shi et al. (2023) Dachuan Shi, Chaofan Tao, Ying Jin, Zhendong Yang, Chun Yuan, and Jiaqi Wang.  UPop: Unified and progressive pruning for compressing vision-language transformers.  In _Proceedings of the 40th International Conference on Machine Learning_ , volume 202, pp. 31292–31311. PMLR, 2023.
  * Simonyan & Zisserman (2014) Karen Simonyan and Andrew Zisserman.  Very deep convolutional networks for large-scale image recognition.  _arXiv preprint arXiv:1409.1556_ , 2014.
  * Song et al. (2022) Zhuoran Song, Yihong Xu, Zhezhi He, Li Jiang, Naifeng Jing, and Xiaoyao Liang.  Cp-vit: Cascade vision transformer pruning via progressive sparsity prediction, 2022.
  * Tang et al. (2020) Yehui Tang, Yunhe Wang, Yixing Xu, Dacheng Tao, Chunjing Xu, Chao Xu, and Chang Xu.  Scop: Scientific control for reliable neural network pruning.  _Advances in Neural Information Processing Systems_ , 33:10936–10947, 2020.
  * Touvron et al. (2021) Hugo Touvron, Matthieu Cord, Matthijs Douze, Francisco Massa, Alexandre Sablayrolles, and Hervé Jégou.  Training data-efficient image transformers & distillation through attention.  In _International conference on machine learning_ , pp. 10347–10357. PMLR, 2021.
  * Vaswani et al. (2017) Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Łukasz Kaiser, and Illia Polosukhin.  Attention is all you need.  _Advances in neural information processing systems_ , 30, 2017.
  * Wang et al. (2019) Alex Wang, Amanpreet Singh, Julian Michael, Felix Hill, Omer Levy, and Samuel R. Bowman.  GLUE: A multi-task benchmark and analysis platform for natural language understanding.  In _International Conference on Learning Representations_ , 2019.  URL https://openreview.net/forum?id=rJ4km2R5t7.
  * Wang et al. (2020a) Hanrui Wang, Zhanghao Wu, Zhijian Liu, Han Cai, Ligeng Zhu, Chuang Gan, and Song Han.  HAT: Hardware-aware transformers for efficient natural language processing.  In _Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics_ , pp. 7675–7688, Online, July 2020a. Association for Computational Linguistics.  doi: 10.18653/v1/2020.acl-main.686.  URL https://aclanthology.org/2020.acl-main.686.
  * Wang et al. (2021) Yi Ru Wang, Samir Khaki, Weihang Zheng, Mahdi S Hosseini, and Konstantinos N Plataniotis.  Conetv2: Efficient auto-channel size optimization for cnns.  In _2021 20th IEEE International Conference on Machine Learning and Applications (ICMLA)_ , pp. 998–1003. IEEE, 2021.
  * Wang et al. (2020b) Ziheng Wang, Jeremy Wohlwend, and Tao Lei.  Structured pruning of large language models.  In _Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP)_. Association for Computational Linguistics, 2020b.  doi: 10.18653/v1/2020.emnlp-main.496.  URL https://doi.org/10.18653%2Fv1%2F2020.emnlp-main.496.
  * Wei et al. (2023) Siyuan Wei, Tianzhu Ye, Shen Zhang, Yao Tang, and Jiajun Liang.  Joint token pruning and squeezing towards more aggressive compression of vision transformers.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , pp. 2092–2101, 2023.
  * Wolf et al. (2020) Thomas Wolf, Lysandre Debut, Victor Sanh, Julien Chaumond, Clement Delangue, Anthony Moi, Pierric Cistac, Tim Rault, Remi Louf, Morgan Funtowicz, Joe Davison, Sam Shleifer, Patrick von Platen, Clara Ma, Yacine Jernite, Julien Plu, Canwen Xu, Teven Le Scao, Sylvain Gugger, Mariama Drame, Quentin Lhoest, and Alexander Rush.  Transformers: State-of-the-art natural language processing.  In _Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing: System Demonstrations_ , pp. 38–45, Online, October 2020. Association for Computational Linguistics.  doi: 10.18653/v1/2020.emnlp-demos.6.  URL https://aclanthology.org/2020.emnlp-demos.6.
  * Xia et al. (2022) Mengzhou Xia, Zexuan Zhong, and Danqi Chen.  Structured pruning learns compact and accurate models.  In _Association for Computational Linguistics (ACL)_ , 2022.
  * Xiao et al. (2023) Guangxuan Xiao, Ji Lin, Mickael Seznec, Hao Wu, Julien Demouth, and Song Han.  SmoothQuant: Accurate and efficient post-training quantization for large language models.  In Andreas Krause, Emma Brunskill, Kyunghyun Cho, Barbara Engelhardt, Sivan Sabato, and Jonathan Scarlett (eds.), _Proceedings of the 40th International Conference on Machine Learning_ , volume 202 of _Proceedings of Machine Learning Research_ , pp. 38087–38099. PMLR, 23–29 Jul 2023.  URL https://proceedings.mlr.press/v202/xiao23c.html.
  * Yang et al. (2023) Huanrui Yang, Hongxu Yin, Maying Shen, Pavlo Molchanov, Hai Li, and Jan Kautz.  Global vision transformer pruning with hessian-aware saliency.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , pp. 18547–18557, 2023.
  * Yu et al. (2022a) Fang Yu, Kun Huang, Meng Wang, Yuan Cheng, Wei Chu, and Li Cui.  Width & depth pruning for vision transformers.  In _AAAI Conference on Artificial Intelligence_ , 2022a.  URL https://api.semanticscholar.org/CorpusID:250294994.
  * Yu & Xiang (2023) Lu Yu and Wei Xiang.  X-pruner: explainable pruning for vision transformers.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , pp. 24355–24363, 2023.
  * Yu et al. (2022b) Shixing Yu, Tianlong Chen, Jiayi Shen, Huan Yuan, Jianchao Tan, Sen Yang, Ji Liu, and Zhangyang Wang.  Unified visual transformer compression.  In _International Conference on Learning Representations_ , 2022b.  URL https://openreview.net/forum?id=9jsZiUgkCZP.
  * Zhang et al. (2022) Qingru Zhang, Simiao Zuo, Chen Liang, Alexander Bukharin, Pengcheng He, Weizhu Chen, and Tuo Zhao.  Platon: Pruning large transformer models with upper confidence bound of weight importance.  In _International Conference on Machine Learning_ , pp. 26809–26823. PMLR, 2022.
  * Zhao et al. (2022) Borui Zhao, Quan Cui, Renjie Song, Yiyu Qiu, and Jiajun Liang.  Decoupled knowledge distillation, 2022.
  * Zhu et al. (2021) Mingjian Zhu, Yehui Tang, and Kai Han.  Vision transformer pruning, 2021.

##  Appendix A Appendix

The appendix is structured to provide details that matches elicitation from
the main text. Experiments and discussions included in the appendix serve as
supplemental information to provide a greater context to claims and
experiments stated in the main text.

###  A.1 Discussing the OPTIN Algorithim

Algorithm 1 demonstrates the base structure for computing and assigning
importance to each of our printable parameters. Once our importance scores
were computed we directly leveraged the mask search algorithm from PTF (Kwon
et al., 2022) as it searches to maximize scores in the partitioned search
space. Their policy partitions the search space by incrementally adding
attention heads in order of importance, and at each step, adding the maximum
number of rank-ordered neurons that will satisfy the cost constraint
$\mathcal{C}(\left[\theta^{\prime}_{0},\theta^{\prime}_{1},\cdots\theta^{\prime}_{n}\right])\leq
C$. By computing the cumulative importance at each step, we easily deduce that
the step with the maximum cumulative importance must be optimal, as any other
configuration would yield a cumulative score less than or equal to that of the
best.

###  A.2 Details on Hyperparamter $\lambda$

In Tab LABEL:tab:ablation_component, we use the $\lambda$ sweep to express
relative magnitude differences between $\mathcal{L}_{MD}$ and
$\mathcal{L}_{KD}$. Based on the reported results, we can conclude that a
larger importance should be weighed on the distillation loss, in particular,
we expect that
$\lfloor\log_{10}(\mathcal{L}_{MD})\rfloor\sim\\{10,100\\}*\lfloor\log_{10}(\mathcal{L}_{KD})\rfloor$
(i.e. the order of magnitude of $\mathcal{L}_{MD}$ should be 10-100 times
larger than that of $\mathcal{L}_{KD}$)

###  A.3 Details on Dataset Choice

In this work, we evaluated the strength of the OPTIN framework on natural
language processing benchmarks, image classification and semantic
segmentation. Across this wide variety of domains, we used different datasets
for the various tasks following from previous works to bolster the performance
of our method.

GLUE Benchmarks The General Language Understanding Evaluation (GLUE) benchmark
(Wang et al., 2019) contains a variety of NLP-related tasks of which we
included: Similarity and Paraphrase Tasks (MRPC STS-B, QQP) and Inference
Tasks (MNLI, QNLI). The dataset distribution widely vary per task. From the
included selection, STS-B is a regression task, MNLI has three classes, and
the remaining tasks include two classes.

ImageNet 1K Benchmarks The ImageNet-1K dataset (Deng et al., 2009) is a widely
used benchmark for image classification, as cited in several works (Zhu et
al., 2021; Goyal et al., 2020; Pan et al., 2021). It contains 1.2 million
training images and 50K validation images across the 1000 classes. Due to its
difficulty, stemming from the number of classes and images, it presents a
perfect benchmarking medium for our one-shot pruning approach.

CIFAR 10 The CIFAR-10(Krizhevsky et al., 2009) datasets are a common benchmark
across both convolutional neural network pruning and model compression works
(Khaki & Luo, 2023; Lin et al., 2020a; Wang et al., 2021). CIFAR10 contains
50K training and 10K validation images spread over 10 classes. Due to the
prominent use of this dataset in benchmarking tasks, we decided to benchmark
our method for fair comparison with SOTA.

Cityscapes The Cityscapes dataset (Cordts et al., 2016) is heavily used for
semantic segmentation tasks, and in particular, contains high-resolution
images of (1024x2048), with roughly 3K training and 500 validation images. In
this paper, our goal was to demonstrate the effects of pruning a downstream
network under the OPTIN framework, and due to the high resolution of
Cityscapes data, we were able to demonstrate improvements in throughput speed
for our pruned segmentation model.

###  A.4 Details on Evaluation Metric Choice

The two main metrics reported in this work are FLOP(s) and Accuracy (or
equivalently mIOU in the case of segmentation). Given the target domain of
this paper, these metrics best express the tradeoff between high accuracy and
computational complexity, and further how the OPTIN framework is better able
to make this distinction. The selected metrics have further been reported in
similar previous works (Kwon et al., 2022; Bolya et al., 2023; Wei et al.,
2023). Finally, we also report im/s throughput to better illustrate the real-
world implications of the OPTIN Framework, especially in resource or time-
constrained environments.

###  A.5 Average Time Analysis

Task |  Dataset |  Model |  Avg. Pruning Time (Hours)
---|---|---|---
Natural Language |  GLUE Benchmark |  BERT |  0.4
Image Classification |  ImageNet-1K |  DeiT Tiny |  0.3
Image Classification |  ImageNet-1K |  DeiT Small |  0.3
Semantic Segmentation |  Cityscapes |  Mask2Former(Swin-Ti) |  0.5
(a)

###  A.6 Ablative Experiments

Dataset |  Batch Size |  Acc.
---|---|---
MNLI |  16 |  82.12
MNLI |  32 |  81.90
MNLI |  64 |  81.73
MNLI |  128 |  82.20
ImageNet |  16 |  70.53
ImageNet |  32 |  71.25
ImageNet |  64 |  71.01
ImageNet |  128 |  70.82
(a)

(b)

Token Merging Alg. |  Scheduler |  $\pm\triangle Acc(\%)$ |  FLOPs(G)
---|---|---|---
Baseline (N/A) |  - |  - |  17.6
Random Prune |  default |  $\downarrow 8.47$ |  11.81
Random Prune |  $\texttt{OPTIN}_{\tau(\infty)}$ |  $\downarrow\textbf{7.11}$ |  11.75
bipartite merge |  default |  $\downarrow 0.80$ |  11.81
bipartite merge |  $\texttt{OPTIN}_{\tau(\infty)}$ |  $\downarrow\textbf{0.52}$ |  11.75
(c)

Table 7: Additional Experiments Here we evaluate three components: (a) the
ablative effect of batch size in computing the distillation loss, (b) a
comparison of the optimal reduction schedule from
$\texttt{OPTIN}_{\tau(\infty)}$ compared to the constant and decreasing
schedules from ToMe. (c) the effect of different patch reduction/merging
techniques using the OPTIN Framework. Our default settings are marked in
green.

###  A.7 Additional Language Experiments

Method | MNLI | QQP | QNLI | SST | STS-B | MRPC
---|---|---|---|---|---|---
$\text{BERT}_{BASE}$ |  84.53 |  91.00 |  91.41 |  93.57 |  88.90 |  86.27
PTF |  81.21 |  89.99 |  88.38 |  92.13 |  87.10 |  83.14
$\textbf{OPTIN}_{\lambda_{c}=0.01}^{\ddagger}$ |  82.12 |  90.08 |  88.54 |  92.36 |  87.19 |  85.21
$\text{PTF}^{\dagger\dagger}$ |  82.51 |  90.35 |  90.06 |  92.49 |  88.00 |  85.27
$\textbf{OPTIN}^{\ddagger\ddagger}$ |  82.74 |  90.43 |  90.35 |  92.73 |  88.21 |  85.68

Table 8: Natural Language Benchmarks. Augments the main table 8 with two
additional experiments. $\textbf{OPTIN}_{\lambda_{c}=0.01}^{\ddagger}$ runs
the OPTIN algorithm with $\lambda_{c}=0.01$ to display the best results we
achieved using our standard framework. Further,
$\textbf{OPTIN}^{\ddagger\ddagger}$ compares with
$\text{PTF}^{\dagger\dagger}$ which includes the mask tuning/scaling from PTF
(Kwon et al., 2022) to discover a non-binary mask that helps to reduce in-
place reconstruction errors. Latency is estimated at $B=32$ and ranges between
1.35-1.38 $\times$ improvement.‡ results are averaged over 5 different seeds.

Task | Attention Heads | Hidden Neurons | Patches&Tokens | Output Channels
---|---|---|---|---
Natural Language Processing |  ✓ |  ✓ |  - |  -
Image Classification (CNN) |  - |  - |  - |  ✓
Image Classification (TF) |  ✓ |  ✓ |  ✓ |  -
Semantic Segmentation |  - |  ✓ |  - |  -
Table 9: Identifying the prunable weights that OPTIN uses to accelerate the
model for various downstream tasks

###  A.8 Extending OPTIN to various downstream tasks

When moving from the language domain to other applications, competitive
methods leverage additional pruning components in order to spread the
compression over a larger search space. In response, we too apply this with
OPTIN. Tab 9 identifies the search space used in OPTIN for various downstream
tasks.

###  A.9 Adapting the Trajectory Formulation to TokenPatch Informativeness

As detailed in Sec 4.2, the OPTIN framework allows users to select the best
token reduction technique for their task to create an expanded prunable search
space. The OPTIN framework adapts to image datasets by further producing an
optimal reduction schedule for tokens that can be leveraged by any reduction
or merging technique. In the main paper, we use ToMe with bipartite matching,
however, we ablate the metric choice and merging strategy in Appendix A.6.

In order to obtain the optimal token reduction, we apply the trajectory
estimation to patches in the vison-transformer models, by simply modifying the
reshaping operator and the dimension upon which we compute the importance. We
adopt the inter-sample representation (Hao et al., 2022) and since we are
determining patch-level importance, it follows that we should compare our base
and pruned embeddings along said dimension. We note that the use of the term
patches in the context of vision-transformers would be represented by the same
dimension as the token sequence length in the language domain. We redefine the
manifold distillation loss according to the index $j$ which ranges up to the
number of patches for the co-responding model. We begin by redefining the
manifold structure relational map based on index $j$ where
$F_{i,[:,j,:]}\in\mathbf{R}^{B\times 1\times D}$ as:

$\displaystyle\mathcal{M}(F_{i,[:,j,:]})=(F_{i,[:,j,:]})(F_{i,[:,j,:]})^{T}$

In particular, we modify the $\mathcal{L}$ inter-image patch distillation loss
from (Hao et al., 2022) by replacing the student input with that of the masked
patch, and the teacher input with the precomuted embeddings from the network.
For two given feature embeddings from layer $i$ for a base and pruned model,
the sample manifold reconstruction error would present as:

$\displaystyle\mathcal{L}_{MD}(F_{i}^{{}^{\prime}},F_{i})$
$\displaystyle=\frac{1}{T}\sum^{T}_{j=0}||\mathcal{M}(F_{i,[:,j,:]}^{{}^{\prime}})-\mathcal{M}(F_{i,[:,j,:]})||^{2}_{F}$

This error is accumulated with standard KL Divergence resulting in a similar
Equation 3.

After determining the importance score for each patch, we can derive the
average number of patches required per layer for maximum information
throughput by simple rank elimination given an FLOPs constraint. After
executing the mask search with attention heads and neurons, we alleviate the
remaining FLOP reduction required by removing tokens in order of ascending
importance (i.e remove the lowest importance first). This ultimately produces
the number of tokens per layer which can be extracted as a token reduction
schedule that can be leveraged on run-time with the ToMe bipartite matching
scheme. We have further shown that the OPTIN Framework reduction scheme is
much more informed than the standard constant or decreasing schemes commonly
used – See Appendix A.6.

###  A.10 Adapting the Trajectory Formulation to Output Channels

To adapt the trajectory estimation to output channels in CNN-style networks,
we reduce the relation to a simple mean-square error computed between the
feature embeddings along the length of the model. In particular, we average
the embeddings along the batch dimension and compute the sum of the mean
squared error between the base and pruned model along each layer deeper in the
network:

$\displaystyle\mathcal{L}_{MD}(F_{i}^{{}^{\prime}},F_{i})=\frac{1}{B}\sum||\sum^{B}F_{i}^{{}^{\prime}}-\sum^{B}F_{i}||^{2}_{F}$

Once again, we are able to plug this into Equation 3 with standard KL
Divergence to determine overall channel importance.


# Bounds for the zeros of Collatz polynomials, with necessary and sufficient
strictness conditions

Matt Hohertz
Department of Mathematics, Rutgers University
<EMAIL_ADDRESS>
##  1 Introduction

Let $c(N)$ be the Collatz iterate of $N$, i.e.,

$c(N):=\begin{cases}\frac{N}{2},&N\mbox{ even}\\\ \frac{3N+1}{2},&N\mbox{ odd
and not $1$}\\\ 0,&N=1.\end{cases}$ (1)

Also let $c^{k}(N)$ have the standard meaning

$c^{k}(N):=\begin{cases}N,&k=0\\\ c\left(c^{k-1}(N)\right),&k\geq
1\end{cases}$ (2)

and define $n(N)$ (just $n$ when $N$ is clear from context) as

$n(N):=\displaystyle\min\\{k\in\mathbb{N}:c^{k}(N)=1\\}.$ (3)

As in Hohertz and Kalantari [2020], we define the $N^{th}$ Collatz polynomial
to be

$P_{N}(z):=\displaystyle\sum_{k=0}^{n}c^{k}(N)\cdot z^{k},$ (4)

i.e., the polynomial whose coefficients are the Collatz iterates of $N$, or
equivalently consecutive members of the Collatz trajectory/sequence of $N$ (we
will assume $N\in\mathbb{N}-\\{0,1\\}$ to avoid the trivial $P_{1}(z)=1$).
Throughout the article, let $z_{N}$ signify an arbitrary root of $P_{N}(z)$
(which we call a Collatz zero), and let $[n]:=[1,n]\cap\mathbb{N}$.

We prove that

$\frac{2M}{3M+1}\leq\left|z_{N}\right|\leq 2,$ (5)

where $M$ is the least odd iterate of $N$ other than 1. In fact, we go
somewhat further, proving that

$\frac{2M}{3M+1}<\left|z_{N}\right|<2$ (6)

with probability $1$ and giving precise conditions under which $N$ belongs to
the sparse set of exceptions.

##  2 General bounds

######  Lemma 1 (Eneström-Kakeya)

Let $f(z)=a_{n}z^{n}+\cdots+a_{1}z+a_{0}$ have all strictly positive
coefficients and set

$\displaystyle\alpha[f]$
$\displaystyle:=\displaystyle\min_{k=0,\cdots,n-1}\frac{a_{k}}{a_{k+1}}$ (7)
$\displaystyle\beta[f]$
$\displaystyle:=\displaystyle\max_{k=0,\cdots,n-1}\frac{a_{k}}{a_{k+1}}.$ (8)

Then

$\alpha[f]\leq\left|w\right|\leq\beta[f]$ (9)

for all roots $w$ of $f(z)$.

###### Proof

See, e.g., Theorem 10 of Laohakosol and Tadee [2014] or Theorem A of Anderson
et al. [1981]. ■

□

With Lemma 1, we prove the following general bound for $\left|z_{N}\right|$:

###### Theorem I

$\frac{2M}{3M+1}\leq\left|z_{N}\right|\leq 2,$ (10)

where $M:=\displaystyle\max\\{-\frac{1}{2},\displaystyle\min_{\ell:\ell\equiv
1(2)}\\{\ell\neq 1\land\ell\mbox{ a Collatz iterate of }N\\}\\}$.

###### Proof

If $a_{k}$ is odd then

$\frac{a_{k}}{a_{k+1}}=\frac{2a_{k}}{3a_{k}+1},$ (11)

and if $a_{k}$ is even then

$\frac{a_{k}}{a_{k+1}}=\frac{2a_{k}}{a_{k}}=2.$ (12)

If $N$ has an odd iterate other than 1 (i.e., $c^{n}(N)$), then the conclusion
follows by Lemma 1. Otherwise, $P_{N}(z)$ is a partial sum of the geometric
series

$N\cdot\left(1+\frac{z}{2}+\cdots+\frac{z^{n}}{2^{n}}\right),$ (13)

whose roots all lie on $\\{z:\left|z\right|=2\\}$. ■

##  3 Strictness of the lower bound

######  Lemma 2 (Theorem B, Anderson et al. [1981])

For a polynomial $f(z)$ of degree $n$ with strictly positive coefficients, let
$S[f]$ be the set of all $j\in[n+1]$ such that

$\beta\left[f\right]>\frac{a_{n-j}}{a_{n+1-j}}.$ (14)

Then the upper bound of Equation (9) is an equality if and only if
$1<d:=\gcd\left(j\in S[f]\right)$, in which case

  * •

all the zeros on $\left|z\right|=\beta[f]$ are simple and given by
$\\{\beta[f]\cdot\exp\left(\frac{2\pi ij}{d}\right),j=1,\cdots,d-1\\}$ and

  * •

$f\left(\beta[f]\cdot z\right)=\left(1+z+\cdots+z^{d-1}\right)\cdot
q_{m}\left(z^{d}\right)$ for a degree $m$ polynomial $q_{m}$ with strictly
positive coefficients.

Moreover, if $m>0$ then all zeros of $q_{m}$ belong to $\mathbb{D}$ and
$\beta[q_{m}]\leq 1$. □

Define the reciprocal polynomial $\tilde{f}$ of the degree $n$ polynomial
$f(z)=a_{n}z^{n}+\cdots+a_{k}z^{k}+\cdots+a_{0}$ to be

$\displaystyle\tilde{f}(z)$ $\displaystyle:=z^{n}\cdot
f\left(\frac{1}{z}\right)$ (15)
$\displaystyle=a_{0}z^{n}+\cdots+a_{n-k}z^{k}+\cdots+a_{n}.$ (16)

Note that

$\displaystyle\beta[\tilde{f}]$
$\displaystyle=\displaystyle\max_{j=0,\cdots,n-1}\frac{a_{n-j}}{a_{n-j-1}}$
(17)
$\displaystyle=\frac{1}{\displaystyle\min_{j=0,\cdots,n-1}\frac{a_{j}}{a_{j+1}}}$
(18) $\displaystyle=\frac{1}{\alpha[f]},$ (19)

and that $f(w)=0\Leftrightarrow\tilde{f}\left(\frac{1}{w}\right)=0$ because
$a_{0}\neq 0$.

###### Theorem II

Equality holds for the leftmost inequality of Equation (10) if and only if $N$
is a power of 2.

###### Proof

We have observed the “if” direction in the proof of Theorem I. For the “only
if” direction, let $M$ again signify the minimum odd iterate of $N$ not equal
to 1. Then

$\frac{1}{\alpha\left[P_{N}\right]}=\frac{3}{2}+\frac{1}{2M}=\beta\left[\tilde{P_{N}}\right].$
(20)

Now, for $j\in[n+1]$,

$\frac{a_{j}}{a_{j-1}}=\begin{cases}\frac{1}{2},&a_{j-1}\mbox{ even and }j\neq
n+1\\\ \frac{3}{2}+\frac{1}{2a_{j-1}},&a_{j-1}\mbox{ odd}\\\
0,&j=n+1,\end{cases}$ (21)

so that $\beta\left[\tilde{P_{N}}\right]>\frac{a_{j}}{a_{j-1}}$ for all $j$
except when $a_{j-1}=M$. Since this equality holds for at least two
consecutive coefficients of $\tilde{P_{N}}$, $\gcd\left(j\in
S[\tilde{P_{N}}]\right)=1$. Therefore, by Lemma 2,
$\beta\left[\tilde{P_{N}}\right]$ is a strict upper bound for the zeros of
$\tilde{P_{N}}$, whence $\alpha\left[\tilde{P_{n}}\right]$ is a strict lower
bound for the zeros of $P_{N}$. ■

##  4 Strictness of the upper bound

For a given $N$, define the set
$T_{N}:=\\{n+1\\}\cup\\{j\in[n]:c^{n-j}(N)\mbox{ is odd}\\}$. Then Lemma 2
implies the following sharpness result:

###### Theorem III

Let $d:=\gcd(j\in T_{N})$. Then the upper bound of Equation (10) is an
equality if and only if $d>1$, in which case

  1. 1.

the zeros of $P_{N}$ on $\\{\left|z\right|=2\\}$ are simple and given
precisely by $\\{2\omega:\omega^{d}=1\land\omega\neq 1\\}$ and

  2. 2.

$P_{N}$ factors as

$P_{N}(2z)=\left(1+z+\cdots+z^{d-1}\right)\cdot Q_{N}(z^{d}),$ (22)

where $Q_{N}$ is a polynomial with positive coefficients. Moreover, if $Q_{N}$
is non-constant then all its zeros lie in $\mathbb{D}$ and $\beta[q_{N}]\leq
1$.

###### Proof

By the proof of Theorem I (and the fact that $a_{-1}=0$ because $P_{N}$ is a
polynomial), the set $T_{N}$ is precisely the set of $j\in[n+1]$ such that
$\frac{a_{n-j}}{a_{n+1-j}}<\beta[P_{N}]=2$. Thus the result follows from
applying Lemma 2. ■

The exacting conditions of Theorem III suggest that zeros on
$\left|z\right|=2$ are rare, and indeed we prove that this is so. First, we
need two lemmas.

###### Lemma 3

For $N\geq 2$ and $k\geq 0$ chosen uniformly at random,

$\mathbb{P}\left(c^{k}\left(N\right)\mbox{ odd}\right)=\frac{1}{2}.$ (23)

###### Proof

The lemma clearly holds for $k=0$. Let $x_{j}$ be a binary bit representing
the parity of $c^{j}\left(N\right)$. By Theorem B of Lagarias [1985], the
function
${\mathbb{Z}/2^{k+1}\mathbb{Z}}\rightarrow{\mathbb{Z}/2^{k+1}\mathbb{Z}}$
defined by

$\overline{N}\rightarrow\left(x_{0},\cdots,x_{k}\right)$ (24)

is a permutation. Therefore, $c^{k}\left(N\right)$ is odd for one half of all
classes of $N$ mod $2^{k+1}$. ■

□

###### Lemma 4

Let $q_{n}$ be the probability that no two consecutive heads are tossed in a
sequence of $n$ tosses of a fair coin. Then

$q_{n}\leq\frac{6}{n}.$ (25)

###### Proof

If $X_{2}$ is the minimum number of tosses in a sequence that contain two
consecutive heads, then $E_{2}:=\mathbb{E}[X_{2}]=6$. Burch [2011] gives the
following proof of this fact:

Let $X_{1}$ be the minimum number of tosses containing one head. Then
$E_{1}:=\mathbb{E}[X_{1}]=2$. After the first head is tossed, there is a $0.5$
probability that the next toss is also heads and a $0.5$ probability that the
next toss is tails. Thus, by the law of total expectation,

$\displaystyle E_{2}$
$\displaystyle=\frac{1}{2}\cdot\left(E_{1}+1\right)+\frac{1}{2}\cdot\left(E_{1}+1+E_{2}\right)$
(26) $\displaystyle=\frac{1}{2}\cdot 3+\frac{1}{2}\cdot\left(3+E_{2}\right)$
(27) $\displaystyle\frac{E_{2}}{2}$ $\displaystyle=3$ (28) $\displaystyle
E_{2}$ $\displaystyle=6.$ (29)

By Markov’s Inequality,

$\mathbb{P}\left(X_{2}\geq n\right)\leq\frac{E_{2}}{n}\leq\frac{6}{n}.$ (30)

Thus the probability that more than $n$ flips are required for two consecutive
heads (equivalently, that a sequence of $n$ flips contains no two consecutive
heads) is no more than $\frac{6}{n}$. ■

□

Since $\mathbb{P}\left(\gcd\left(j\in T\right)=1\right)\geq q_{n}$,

###### Lemma 5

Let $s_{N}:=\mathbb{P}\left(P_{N}\mbox{ has a root on }|z|=2\right)$. Then

$s_{N}\leq\frac{6\log
2}{\log\left(2N\right)}\approx\frac{4.1589}{\log\left(2N\right)}.$ (31)

###### Proof

If two consecutive coefficients of $P_{N}$ are odd, then $\gcd\left(j\in
T_{N}\right)=1$. By the contrapositive of this statement; Theorem III; and
Lemmas 3 and 4,

$s_{N}=\mathbb{P}\left(\gcd\left(j\in
T_{N}\right)>1\right)\leq\frac{6}{n\left(N\right)+1}.$ (32)

On the other hand, $n\left(N\right)\geq\frac{\log N}{\log 2}$ because this
rightmost quantity is the number of divisions required for a power of two to
converge to 1 under the Collatz sequence. So

$\displaystyle s_{N}$ $\displaystyle\leq\frac{6}{\frac{\log N}{\log 2}+1}$
(33) $\displaystyle\leq\frac{6\log 2}{\log N+\log 2}$ (34)
$\displaystyle\leq\frac{6\log 2}{\log\left(2N\right)}.$ (35)

■

□

###### Theorem IV

The set of $N$ such that $P_{N}$ has a root on $\left|z\right|=2$ has density
0 in the natural numbers.

###### Proof

For integers $N$ chosen uniformly in $[2,n]\cap\mathbb{N}$, the probability
that $P_{N}$ has a root on $\left|z\right|=2$ is no more than

$\frac{1}{n-1}\cdot\displaystyle\sum_{t=2}^{n}\frac{6\log
2}{\log\left(2t\right)}.$ (36)

Because $\frac{1}{\log t}$ is decreasing, this quantity has upper bound

$\displaystyle\frac{6\log
2}{n-1}\cdot\int_{1}^{n}\frac{dt}{\log\left(2t\right)}$
$\displaystyle=\frac{3\log
2}{n-1}\cdot\int_{2}^{2n}\frac{du}{\log\left(u\right)}$ (37)
$\displaystyle=\frac{3\log 2}{n-1}\cdot Li(2n).$ (38)

By the well-known approximation $\frac{Li(n)}{n}=\frac{1}{\log
n}+O\left(\frac{1}{\log^{2}n}\right)$, the quantity of Equation (36) decreases
to 0 as $n\rightarrow\infty$; the conclusion follows. ■

##  5 Final remarks and questions for further study

We conclude with a few open questions:

  1. 1.

Strengthen Theorem II by finding an explicit, closed-form lower bound for
$\left|z_{N}\right|$ in terms of $N$.

  2. 2.

Strengthen Theorems III and IV by finding an explicit, closed-form upper bound
for $\left|z_{N}\right|$ in terms of $N$.

Figure 1: Complex plot of the zeros of $P_{N}$ for $2\leq N\leq 2^{16}$.

  3. 3.

Figure 1 suggests that certain subsets of $\\{\left|z\right|\leq 2\\}$ contain
large clusters of Collatz zeros, while others are zero-free. Give an algorithm
for proving that a subset of $\\{\left|z\right|\leq 2\\}$ is dense with
Collatz zeros (or is zero-free).

  4. 4.

While no Collatz zero can be positive real (due to Descartes’ Rule of Signs),
there appears to be a sequence of zeros that approach $z=1$ arbitrarily
closely, bounded by a parabola with vertex at $z=1$. Prove/disprove the
existence of such a convergent sequence and parabola.

  5. 5.

Under some modest assumptions (which do not necessarily include independence),
the zeros of a polynomial with random coefficients cluster near the unit
circle with uniform angular distribution [Hughes and Nikeghbali, 2008]. Prove
or disprove that these assumptions hold for the Collatz polynomials.

  6. 6.

Prove that some property of Collatz zeros is equivalent to the Collatz
conjecture itself (or to a substantial but weaker conjecture, such as the non-
existence of cycles).

  7. 7.

Find the Galois groups of $P_{N}$ for general classes of $P_{N}$.

  8. 8.

Expanding on Theorem III, find conditions under which $P_{N}$ has zeros at
multiples of roots of unity.

## References

  * Hohertz and Kalantari [2020] Matt Hohertz and Bahman Kalantari.  Collatz polynomials: an introduction with bounds on their zeros.  2020\.
  * Laohakosol and Tadee [2014] Vichian Laohakosol and Suton Tadee.  Algebraic numbers satisfying polynomials with positive rational coefficients.  _Journal of Numbers_ , 2014, 2014.  URL http://downloads.hindawi.com/archive/2014/296828.pdf.
  * Anderson et al. [1981] N. Anderson, E. B. Saff, and R. S. Varga.  An extension of the Eneström-Kakeya theorem and its sharpness.  _SIAM Journal on Mathematical Analysis_ , 12(1):10–22, 1981.  doi: 10.1137/0512002.
  * Lagarias [1985] Jeffrey C. Lagarias.  The $3x+1$ problem and its generalizations.  _The American Mathematical Monthly_ , 92:3–23, 1985.  doi: 10.2307/2322189.  URL http://www.cecm.sfu.ca/organics/papers/lagarias/index.html.  As reprinted in Conference on Organic Mathematics, Canadian Math. Society Conference Proceedings, vol. 20, 1997, pp. 305-331, and posted online at http://www.cecm.sfu.ca/organics/papers/lagarias/index.html.
  * Burch [2011] Jared Burch.  Consecutive successes: a recursive approach.  _Teaching Statistics_ , 33(3):76–77, 2011.  doi: 10.1111/j.1467-9639.2009.00399.x.
  * Hughes and Nikeghbali [2008] C. P. Hughes and A. Nikeghbali.  The zeros of random polynomials cluster uniformly near the unit circle.  _Compositio Mathematica_ , 144(3):734–746, 2008\.  doi: 10.1112/s0010437x07003302.


* Katsura  _et al._ [2010] H. Katsura, N. Nagaosa, and P. A. Lee, Theory of the thermal hall effect in quantum magnets, Phys. Rev. Lett. 104, 066403 (2010).
  * Shindou  _et al._ [2013a] R. Shindou, R. Matsumoto, S. Murakami, and J.-i. Ohe, Topological chiral magnonic edge mode in a magnonic crystal, Phys. Rev. B 87, 174427 (2013a).
  * Shindou  _et al._ [2013b] R. Shindou, J.-i. Ohe, R. Matsumoto, S. Murakami, and E. Saitoh, Chiral spin-wave edge modes in dipolar magnetic thin films, Phys. Rev. B 87, 174402 (2013b).
  * Zhang  _et al._ [2013] L. Zhang, J. Ren, J.-S. Wang, and B. Li, Topological magnon insulator in insulating ferromagnet, Phys. Rev. B 87, 144101 (2013).
  * Mook  _et al._ [2014a] A. Mook, J. Henk, and I. Mertig, Magnon hall effect and topology in kagome lattices: A theoretical investigation, Phys. Rev. B 89, 134409 (2014a).
  * Shindou and Ohe [2014] R. Shindou and J.-i. Ohe, Magnetostatic wave analog of integer quantum hall state in patterned magnetic films, Phys. Rev. B 89, 054412 (2014).
  * Mook  _et al._ [2014b] A. Mook, J. Henk, and I. Mertig, Edge states in topological magnon insulators, Phys. Rev. B 90, 024412 (2014b).
  * Nakata  _et al._ [2017a] K. Nakata, J. Klinovaja, and D. Loss, Magnonic quantum hall effect and wiedemann-franz law, Phys. Rev. B 95, 125429 (2017a).
  * Nakata  _et al._ [2017b] K. Nakata, S. K. Kim, J. Klinovaja, and D. Loss, Magnonic topological insulators in antiferromagnets, Phys. Rev. B 96, 224414 (2017b).
  * Mook  _et al._ [2018] A. Mook, B. Göbel, J. Henk, and I. Mertig, Taking an electron-magnon duality shortcut from electron to magnon transport, Phys. Rev. B 97, 140401 (2018).
  * Mook  _et al._ [2019] A. Mook, J. Henk, and I. Mertig, Thermal hall effect in noncollinear coplanar insulating antiferromagnets, Phys. Rev. B 99, 014427 (2019).
  * van Hoogdalem  _et al._ [2013] K. A. van Hoogdalem, Y. Tserkovnyak, and D. Loss, Magnetic texture-induced thermal hall effects, Phys. Rev. B 87, 024402 (2013).
  * Roldán-Molina  _et al._ [2016] A. Roldán-Molina, A. S. Nunez, and J. Fernández-Rossier, Topological spin waves in the atomic-scale magnetic skyrmion crystal, New Journal of Physics 18, 045015 (2016).
  * Garst  _et al._ [2017] M. Garst, J. Waizner, and D. Grundler, Collective spin excitations of helices and magnetic skyrmions: review and perspectives of magnonics in non-centrosymmetric magnets, Journal of Physics D: Applied Physics 50, 293002 (2017).
  * Díaz  _et al._ [2019] S. A. Díaz, J. Klinovaja, and D. Loss, Topological magnons and edge states in antiferromagnetic skyrmion crystals, Phys. Rev. Lett. 122, 187203 (2019).
  * Kim  _et al._ [2019] S. K. Kim, K. Nakata, D. Loss, and Y. Tserkovnyak, Tunable magnonic thermal hall effect in skyrmion crystal phases of ferrimagnets, Phys. Rev. Lett. 122, 057204 (2019).
  * Díaz  _et al._ [2020] S. A. Díaz, T. Hirosawa, J. Klinovaja, and D. Loss, Chiral magnonic edge states in ferromagnetic skyrmion crystals controlled by magnetic fields, Phys. Rev. Research 2, 013231 (2020).
  * Li  _et al._ [2016] F.-Y. Li, Y.-D. Li, Y. B. Kim, L. Balents, Y. Yu, and G. Chen, Weyl magnons in breathing pyrochlore antiferromagnets, Nature Communications 7, 12691 (2016).
  * Mook  _et al._ [2016] A. Mook, J. Henk, and I. Mertig, Tunable magnon weyl points in ferromagnetic pyrochlores, Phys. Rev. Lett. 117, 157204 (2016).
  * Mook  _et al._ [2021] A. Mook, S. A. Díaz, J. Klinovaja, and D. Loss, Chiral hinge magnons in second-order topological magnon insulators, Phys. Rev. B 104, 024406 (2021).
  * Mook  _et al._ [2015a] A. Mook, J. Henk, and I. Mertig, Magnon waveguide with nanoscale confinement constructed from topological magnon insulators, Phys. Rev. B 91, 174409 (2015a).
  * Mook  _et al._ [2015b] A. Mook, J. Henk, and I. Mertig, Topologically nontrivial magnons at an interface of two kagome ferromagnets, Phys. Rev. B 91, 224411 (2015b).
  * Xu  _et al._ [2016] B. Xu, T. Ohtsuki, and R. Shindou, Integer quantum magnon hall plateau-plateau transition in a spin-ice model, Phys. Rev. B 94, 220403 (2016).
  * Iacocca and Heinonen [2017] E. Iacocca and O. Heinonen, Topologically nontrivial magnon bands in artificial square spin ices with dzyaloshinskii-moriya interaction, Phys. Rev. Applied 8, 034015 (2017).
  * Li  _et al._ [2018b] Z.-X. Li, C. Wang, Y. Cao, and P. Yan, Edge states in a two-dimensional honeycomb lattice of massive magnetic skyrmions, Phys. Rev. B 98, 180407 (2018b).
  * Li  _et al._ [2018c] Y.-M. Li, J. Xiao, and K. Chang, Topological magnon modes in patterned ferrimagnetic insulator thin films, Nano Letters 18, 3032 (2018c).
  * Mellado [2022] P. Mellado, Intrinsic topological magnons in arrays of magnetic dipoles, Scientific Reports 12, 1420 (2022).
  * Chisnell  _et al._ [2015] R. Chisnell, J. S. Helton, D. E. Freedman, D. K. Singh, R. I. Bewley, D. G. Nocera, and Y. S. Lee, Topological magnon bands in a kagome lattice ferromagnet, Phys. Rev. Lett. 115, 147201 (2015).
  * Chen  _et al._ [2018] L. Chen, J.-H. Chung, B. Gao, T. Chen, M. B. Stone, A. I. Kolesnikov, Q. Huang, and P. Dai, Topological spin excitations in honeycomb ferromagnet ${\mathrm{cri}}_{3}$, Phys. Rev. X 8, 041028 (2018).
  * Zhu  _et al._ [2021] F. Zhu, L. Zhang, X. Wang, F. J. dos Santos, J. Song, T. Mueller, K. Schmalzl, W. F. Schmidt, A. Ivanov, J. T. Park, J. Xu, J. Ma, S. Lounis, S. Blügel, Y. Mokrousov, Y. Su, and T. Brückel, Topological magnon insulators in two-dimensional van der waals ferromagnets crsite3 and crgete3: Toward intrinsic gap-tunability, Science Advances 7 (2021).
  * Malki and Uhrig [2020] M. Malki and G. S. Uhrig, Topological magnetic excitations, Europhysics Letters 132, 20003 (2020).
  * Li  _et al._ [2021] Z.-X. Li, Y. Cao, and P. Yan, Topological insulators and semimetals in classical magnetic systems, Physics Reports 915, 1 (2021).
  * McClarty [2022] P. A. McClarty, Topological magnons: A review, Annual Review of Condensed Matter Physics 13, 171 (2022).
  * Wang and Wang [2021] X. S. Wang and X. R. Wang, Topological magnonics, Journal of Applied Physics 129, 151101 (2021).
  * Dzyaloshinsky [1958] I. Dzyaloshinsky, A thermodynamic theory of “weak” ferromagnetism of antiferromagnetics, Journal of Physics and Chemistry of Solids 4, 241 (1958).
  * Moriya [1960] T. Moriya, Anisotropic superexchange interaction and weak ferromagnetism, Phys. Rev. 120, 91 (1960).
  * Haldane [1988] F. D. M. Haldane, Model for a quantum Hall effect without landau levels: Condensed-matter realization of the “parity anomaly”, Phys. Rev. Lett. 61, 2015 (1988).
  * Owerre [2016] S. A. Owerre, A first theoretical realization of honeycomb topological magnon insulator, J. Phys.: Condens. Matter 28, 386001 (2016).
  * Holstein and Primakoff [1940] T. Holstein and H. Primakoff, Field dependence of the intrinsic domain magnetization of a ferromagnet, Phys. Rev. 58, 1098 (1940).
  * Pantaleón and Xian [2017] P. A. Pantaleón and Y. Xian, Analytical study of the edge states in the bosonic haldane model, Journal of Physics: Condensed Matter 29, 295701 (2017).
  * Hatsugai [1993a] Y. Hatsugai, Chern number and edge states in the integer quantum Hall effect, Phys. Rev. Lett. 71, 3697 (1993a).
  * Hatsugai [1993b] Y. Hatsugai, Edge states in the integer quantum Hall effect and the Riemann surface of the Bloch function, Phys. Rev. B 48, 11851 (1993b).
  * Note [1] We have chosen armchair rather than zigzag termination because the latter does not support a chiral edge mode at zero momentum, a property that turns out to be crucial to couple the edge mode to a QD.
  * Pershoguba  _et al._ [2018] S. S. Pershoguba, S. Banerjee, J. C. Lashley, J. Park, H. Ågren, G. Aeppli, and A. V. Balatsky, Dirac magnons in honeycomb ferromagnets, Phys. Rev. X 8, 011010 (2018).
  * Pantaleón and Xian [2018] P. A. Pantaleón and Y. Xian, Effects of edge on-site potential in a honeycomb topological magnon insulator, Journal of the Physical Society of Japan 87, 064005 (2018).
  * Pantaleón and Xian [2018] P. A. Pantaleón and Y. Xian, Edge states in a ferromagnetic honeycomb lattice with armchair boundaries, Physica B: Condensed Matter 530, 191 (2018).
  * Karenowska  _et al._ [2016] A. D. Karenowska, A. V. Chumak, A. A. Serga, and B. Hillebrands, Magnon spintronics, in  _Handbook of Spintronics_, edited by Y. Xu, D. D. Awschalom, and J. Nitta (Springer Netherlands, Dordrecht, 2016) pp. 1505–1549.
  * Prabhakar and Stancil [2009] A. Prabhakar and D. D. Stancil,  _Spin waves: Theory and applications_, Vol. 5 (Springer, 2009).
  * Dubs  _et al._ [2017] C. Dubs, O. Surzhenko, R. Linke, A. Danilewsky, U. Brückner, and J. Dellith, Sub-micrometer yttrium iron garnet LPE films with low ferromagnetic resonance losses, Journal of Physics D: Applied Physics 50, 204005 (2017).
  * Golovach  _et al._ [2006] V. N. Golovach, M. Borhani, and D. Loss, Electric-dipole-induced spin resonance in quantum dots, Phys. Rev. B 74, 165319 (2006).
  * Nowack  _et al._ [2007] K. C. Nowack, F. H. L. Koppens, Y. V. Nazarov, and L. M. K. Vandersypen, Coherent control of a single electron spin with electric fields, Science 318, 1430 (2007).
  * Nadj-Perge  _et al._ [2010] S. Nadj-Perge, S. M. Frolov, E. P. A. M. Bakkers, and L. P. Kouwenhoven, Spin–orbit qubit in a semiconductor nanowire, Nature 468, 1084 (2010).
  * Schroer  _et al._ [2011] M. D. Schroer, K. D. Petersson, M. Jung, and J. R. Petta, Field tuning the $g$ factor in inas nanowire double quantum dots, Phys. Rev. Lett. 107, 176811 (2011).
  * Note [2] Here, we estimate the dipole-field-induced Rabi frequency to be tens of megahertz. In the case of EDSR the Rabi frequency is given by $\nu_{\text{Rabi}}=\hbar^{-1}E_{\text{SO}}(eE_{y}l_{y})\Delta\Delta^{-2}_{\text{orb}}$ , if the driving field is applied in the $y$ direction. In order to estimate the dipole-interaction-induced Rabi frequency, we used $E_{y}=0.5\,$V/$\mu$m for the amplitude of the drive and $E_{\text{SO}}=0.2\,\mu$eV, that is the maximal coupling (as a function of $d_{y}$ for our set of parameters) that the inhomogeneous dipole-field $B_{\text{eff}}^{y}$ can induce between harmonic oscillator basis states in the $y$ direction.
  * Bravyi  _et al._ [2011] S. Bravyi, D. P. DiVincenzo, and D. Loss, Schrieffer–Wolff transformation for quantum many-body systems, Annals of Physics 326, 2793 (2011).
  * Makhlin  _et al._ [2003] Y. Makhlin, G. Schön, and A. Shnirman, Dissipation in josephson qubits, New Directions in Mesoscopic Physics (Towards Nanoscience) , 197 (2003).
  * Poyatos  _et al._ [1997] J. F. Poyatos, J. I. Cirac, and P. Zoller, Complete characterization of a quantum process: The two-bit quantum gate, Phys. Rev. Lett. 78, 390 (1997).
  * Note [3] Within the present assumptions the detuning from resonance would change as $\delta=\frac{S|J^{\perp}|}{2}\\{\erf[d_{y}/l_{y}]+\erf[(L_{y}-d_{y})/l_{y}]\\}-\varepsilon_{0}$. Note that depending on the value $J^{\perp}$, the resonance can be reached at any $d_{y}$ in principle.
  * Lindblad [1976] G. Lindblad, On the generators of quantum dynamical semigroups, Communications in Mathematical Physics 48, 119 (1976).
  * Note [4] The choice of the rise time is a crucial step in order to create a magnon wave packet that can be efficiently absorbed by the second qubit. We found that a pulse with (relatively) long $t_{\text{rise}}$ time creates a more symmetric wave packet that can be absorbed with a higher accuracy (i.e., magnon number reduces close to zero after absorption).
  * Note [5] Since the first qubit is coupled to the first unit cell and the second to the last unit cell, the effective qubit-qubit distance in the simulation is $d=42l_{x}\sim 510\,$nm.
  * Blais  _et al._ [2021] A. Blais, A. L. Grimsmo, S. M. Girvin, and A. Wallraff, Circuit quantum electrodynamics, Rev. Mod. Phys. 93, 025005 (2021).
  * Kim and Tserkovnyak [2017] S. K. Kim and Y. Tserkovnyak, Chiral edge mode in the coupled dynamics of magnetic solitons in a honeycomb lattice, Phys. Rev. Lett. 119, 077204 (2017).