# Sparsifiner: Learning Sparse Instance-Dependent Attention
for Efficient Vision Transformers

Cong Wei1 Brendan Duke1,311footnotemark: 1 Ruowei Jiang3 Parham Aarabi1,3
Graham W. Taylor2,4 Florian Shkurti1,4 Equal contribution. 1University of
Toronto  2University of Guelph  3Modiface, Inc  4Vector Institute

###### Abstract

Vision Transformers (ViT) have shown their competitive advantages performance-
wise compared to convolutional neural networks (CNNs) though they often come
with high computational costs. To this end, previous methods explore different
attention patterns by limiting a fixed number of spatially nearby tokens to
accelerate the ViT’s multi-head self-attention (MHSA) operations. However,
such structured attention patterns limit the token-to-token connections to
their spatial relevance, which disregards learned semantic connections from a
full attention mask. In this work, we propose a novel approach to learn
instance-dependent attention patterns, by devising a lightweight connectivity
predictor module to estimate the connectivity score of each pair of tokens.
Intuitively, two tokens have high connectivity scores if the features are
considered relevant either spatially or semantically. As each token only
attends to a small number of other tokens, the binarized connectivity masks
are often very sparse by nature and therefore provide the opportunity to
accelerate the network via sparse computations. Equipped with the learned
unstructured attention pattern, sparse attention ViT (Sparsifiner) produces a
superior Pareto-optimal trade-off between FLOPs and top-1 accuracy on ImageNet
compared to token sparsity. Our method reduces 48% $\sim$ 69% FLOPs of MHSA
while the accuracy drop is within 0.4%. We also show that combining attention
and token sparsity reduces ViT FLOPs by over 60%.

##  1 Introduction

Figure 1: Comparison of Sparsifiner and fixed attention patterns. Twins [10]
(a), Swin [22] (b), and Axial [16] (c) address quadratic MHSA complexity using
fixed attention patterns, which does not consider the instance-dependent
nature of semantic information in images. To address this, we propose
Sparsifiner (d): an efficient module for sparse instance-dependent attention
pattern prediction.

Vision Transformers (ViTs) [13] have emerged as a dominant model for
fundamental vision tasks such as image classification [13], object detection
[3], and semantic segmentation [7, 6]. However, scaling ViTs to a large number
of tokens is challenging due to the quadradic computational complexity of
multi-head self-attention (MHSA) [35]. This is particularly disadvantageous
for large-scale vision tasks because computing on high-resolution and high-
dimensionality inputs is desirable. For example, input modalities such as
video frames and 3D point clouds have a large number of tokens even for basic
use cases. Novel algorithms are needed to continue to scale ViTs to larger,
more complex vision tasks.

Prior works have largely taken two approaches to improve the computational
efficiency of ViTs: token pruning and using fixed sparse attention patterns in
MHSA. Token pruning methods [27] reduce the number of tokens by a fixed ratio
called the keep rate, but accuracy degrades quickly when pruning early layers
in the network [15, 30, 31]. For example, introducing token pruning into
shallower layers of EViT [15] causes a significant $3.16$% top-1 accuracy drop
on ImageNet [12]. This issue is due to the restriction of pruning an entire
token, which account to pruning an entire row and column of the attention
matrix at once. One way to alleviate this is to prune individual
connectivities of the attention matrix instead of entire tokens. Existing
methods that take this attention matrix connectivity-pruning approach use
fixed sparse attention patterns [8]. For example, local and strided fixed
attention patterns are used [8, 14], in combination with randomly-initialized
connectivities [40]. However, such fixed attention patterns limit the the
capacity of the self-attention connections to a fixed subset of tokens (Fig.
1). These attention patterns’ fixed nature is less effective compared with the
direct communication between tokens in full self attention. For example, Swin
transformer [22, 21] has a limited receptive field at shallower layers and
needs many layers to model long-range dependencies. And BigBird [40] needs to
combine multiple fixed attention patterns to achieve good performance. Rather,
it is desirable to design sparse attention algorithms that mimic full self
attention’s instance-dependent nature [35], thereby capturing the variable
distribution of semantic information in the input image content.

To address aforementioned challenges, we propose a method called Sparsifiner
that learns to compute sparse connectivity patterns over attention that are
both instance-dependent and unstructured. The instance-dependent nature of the
attention pattern allows each token to use its limited attention budget of
nonzero elements more efficiently compared to fixed sparse attention patterns.
For example, in attention heads that attend to semantic rather than positional
content [35, 36], tokens containing similar semantic information should be
considered to have high connectivity scores despite their spatial distance.
Similarly, nearby tokens with irrelevant semantic relation should have lower
connectivity scores despite their spatial proximity. Furthermore, Sparsifiner
improves attention pattern flexibility compared to token pruning by pruning
individual connectivities, instead of entire rows and columns of the attention
matrix. This allows Sparsifiner to reduce FLOPs in the early layers of the
network without incurring significant top-1 accuracy degradation (§4). By
pruning individual connectivities dependent on image content, Sparsifiner
generalizes prior approaches to sparsifying MHSA in ViTs, and in doing so
produces a favourable trade-off between accuracy and FLOPs.

Our contributions can be summarized as:

  * •

We propose a novel efficient algorithm called Sparsifiner to predict instance-
dependent sparse attention patterns using low-rank connectivity patterns. Our
investigation into instance-dependent unstructured sparsity is to the best of
our knowledge novel in the context of ViTs.

  * •

We show that such learned unstructured attention sparsity produces a superior
Pareto-optimal tradeoff between FLOPs and top-1 accuracy on ImageNet compared
to token sparsity. Furthermore, we show that Sparsifiner is complementary to
token sparsity methods, and the two approaches can be combined to achieve
superior performance-accuracy tradeoffs.

  * •

We propose a knowledge distillation-based approach for training Sparsifiner
from pretrained ViTs using a small number of training epochs.

##  2 Related Work

Efficient Attention — Developing an efficient attention mechanism for high
resolution image encoding is the focus of this work. Efficient attention
mechanisms have been widely studied in NLP tasks to model long sequences. They
can be categorized as follows: Low-rank methods such as Linformer [37] use a
low-rank projection to linearize the multi-head attention operation. Linformer
[37] replaces the scaled dot product with linear attention that approximates
the attention with a low-rank matrix. Kernelization, including Performer [9],
Linear Transformers [18], and Random Feature Attention [24] use kernels to
avoid explicitly computing the attention matrix. Sparse attention with fixed
attention patterns [8, 16, 23, 25, 10]. This type of technique sparsifies the
attention matrix by limiting the field of view to predefined patterns such as
local and strided windows. Similarity and clustering-based methods including
Routing Transformer [29], Reformer [19], and Sinkhorn Transformer [33]. These
models measure token relevance by sorting or clustering and then assign tokens
to buckets for within-bucket attention. Neural memory mechanisms such as Set
Transformer [20], Compressive Transformer [26], and Longformer [1]. These use
extra global tokens that gather long-range information as a model memory.

Vision Transformers — Recent progress has demonstrated that variants of
Transformers [35] can also be competitive alternatives to CNNs and achieve
promising results on different vision tasks. In addition to image
classification, Transformers have also been applied to various vision tasks,
including object detection [4, 11, 44, 46], image generation [5, 23], and
video processing [42, 45]. Vision Transformer (ViT) [13] splits images as
small patches and treats the patches as the input word tokens. ViT shows
better performance than CNN-type models with sufficient extensive training
data. DeiT [34] incorporates knowledge distillation techniques into ViT
training so that we can train a competitive Transformer using only ImageNet-1k
[12]. LV-ViT [17] further improves the performance of ViT by introducing a new
training objective named token labelling. Most of these methods have quadratic
complexity of self-attention with respect to the input image size.

Efficient Vision Transformers — There is a thrust to model long sequences of
image patches at much higher resolutions. Recent works such as Pyramid Vision
Transformer (PVT) [38], Swin-Transformer [22], T2T-ViT [39], and Vision
Longformer (ViL) [43] apply transformer layers on different resolution scales
by stacking a pyramid of ViTs to form a multi-scale architecture. To achieve
linear complexity, Swin-Transformer [22] uses shifted local window attention.
Vision Longformer [43] adapts the local attention pattern with the global
memory tokens from Longformer [1]. TimeSformer [2] applies multiple
attentions, each along a single axis of the input video. Those methods all
leverage fixed, predefined attention patterns to reduce the quadratic cost. In
contrast, our method generates sparse dynamic attention patterns based on the
input content. Another group of works reduce the number of tokens by pruning
[15, 27, 32], or merging tokens [28, 30, 41]. Recent work, DynamicViT [27] and
EViT [15] study unstructured token sparsification by gradually dropping tokens
in the inference of ViTs [13]. However, quadratic attention cost remains in
early layers where input tokens cannot be largely sparsified. Our method
instead prunes connectivities at every layer, allowing complexity savings at
early layers.

##  3 Method

Figure 2: Single head comparison of the MHSA module for naïve MHSA [35],
Linformer [37], and Sparsifiner. Naïve MHSA incurs quadratic $O(n^{2})$
complexity in the number of tokens $n$. Linformer reduces the complexity to
linear $O(nn_{\text{down}})$ by using a projection of the key and value
matrices to projected key $K^{\text{proj}}\in\mathbb{R}^{n_{\text{down}}\times
d}$ and value $V^{\text{proj}}\in\mathbb{R}^{n_{\text{down}}\times d}$
matrices in a low-rank approximation of the attention matrix. Sparsifiner’s
key insight is to use the low-rank approximation to learn a sparse
connectivity mask $M\in\mathbb{R}^{n\times n}$ and sparse up-projection basis
$W^{\text{up}}$. Using sparse matrix multiplication, Sparsifiner reduces
overall MHSA FLOPs relative to Linformer without restricting the attention
matrix to be low rank. Note that in the rightmost column only (Sparsifiner),
the attention matrix $A$ is not explicitly constructed, and rather is used to
represent sparse attention reconstruction (Eq. 5).

Our proposed method to learn sparse attention patterns, Sparsifiner, consists
of a normal ViT [13] as the backbone with sparse attention modules at each
layer. Our sparse attention module consists of a connectivity mask predictor
and a sparse multi-head self-attention (MHSA) module. In both training and
inference, we generate a sparse connectivity mask by restricting the number of
connections predicted by the mask predictor according to a hyperparameter
budget size $B$. Following this, a sparse MHSA module is used to perform
sparse attention based on the connectivity mask. The sparse MHSA module
implements an efficient computation using a sparse element-wise product
between the full attention map and the sparse connectivity mask to produce a
sparse reconstructed attention map. Then, a sparse-dense attention-value
product between the sparse reconstructed attention map and the value matrix
produces the output of the sparse MHSA module.

For clarity, in the following we describe MHSA for a single attention head
only. In practice, we apply the proposed method to each attention head in a
ViT. We concatenate the resulting output values from all attention heads and
feed them to a linear layer to produce the input to the next transformer layer
[35].

ViT Architecture and Naïve MHSA — We base our method on the existing ViT model
architecture [13] and naïve implementation of MHSA [35]. A ViT first tokenizes
an input image $I\in\mathbb{R}^{h\times w\times 3}$ into a set of $n$ tokens
$X\in\mathbb{R}^{n\times d}$, each with dimension $d$. Each token consists of
a patch embedding, retrieved via linear projection of the non-overlapping
image patches, and a positional encoding. The resulting sequence of tokens is
then fed into MHSA modules to compute the attention matrix
$A\in\mathbb{R}^{n\times n}$ as the product of query $Q\in\mathbb{R}^{n\times
d}=X^{l}W^{Q}$ and key $K\in\mathbb{R}^{n\times d}=X^{l}W^{K}$ matrices, where
the learned projection matrices $W^{Q}\in\mathbb{R}^{d\times d}$ and
$W^{K}\in\mathbb{R}^{d\times d}$ compute query and key as projections of the
input $X^{l}\in\mathbb{R}^{n\times d}$ to layer $l$. Naïve MHSA then computes
the attention matrix $A$ as the softmax of outer product of query and key
matrices as shown in the left part of Fig. 2.

Connectivity Mask Predictor — To enable instance-dependent and meaningful
attention patterns while limiting the number of connections, we train a
connectivity mask predictor and achieve sparsity by thresholding.
Specifically, we first compute the low-rank approximation
$A^{\text{down}}\in\mathbb{R}^{n\times n_{\text{down}}}$ of the attention
matrix $A$

$A^{\text{down}}=\text{softmax}\bigg{(}\frac{Q{(W^{\text{down}}K)}^{\top}}{\sqrt{d}}\bigg{)},$
(1)

which we sparsify by thresholding:

$\tilde{A}^{\text{down}}_{ij}=\begin{cases}A^{\text{down}}_{ij}&\text{if
}A^{\text{down}}_{ij}>\tau\\\ 0&\text{otherwise}\end{cases}.$ (2)

In the low-rank attention computation (Eq. 1), we first down-project the token
dimension of key matrix $K$ to a lower dimension $n_{\text{down}}$ using a
learned projection matrix $W^{\text{down}}\in\mathbb{R}^{n_{\text{down}}\times
n}$. Then, a low-rank approximation of the attention matrix is computed from
the outer product of query and down-projected key matrices. Note that in the
low-rank attention sparsification (Eq. 2), with a sparse matrix representation
we need not explicitly store the zeros.

Next, the connectivity mask predictor (Eq. 3) performs a sparse matrix
multiplication of a sparse up-projection matrix
$W^{\text{up}}\in\mathbb{R}^{n_{\text{down}}\times n}$ followed by
binarization. This produces an up-projected sparse connectivity mask:

$M=\mathbf{1}\bigg{[}\text{Top-}k(\tilde{A}^{\text{down}}W^{\text{up}})\bigg{]}.$
(3)

Here, $\tilde{A}^{\text{down}}W^{\text{up}}$ denotes sparse-sparse matrix
multiplication, which is efficiently computed. Our key insight is that the
post-softmax low-rank attention matrix (Eq. 1) should naturally be sparse. We
show an example in Fig. 7.

We apply top-$k$ on the up-projected sparse attention matrix
$\tilde{A}^{\text{down}}W^{\text{up}}$, which is the attention connectivity
score map. $k$ is set to the budget size $B$. We discard zero values and
binarize to produce a sparse low-rank connectivity mask
$M\in\mathbb{R}^{n\times n}$. We indicate binarization by the indicator
function $\mathbf{1}[\cdot]$ in the connectivity mask predictor (Eq. 3).

Sparse MHSA — In Fig. 2, we compare our method to naïve MHSA [35] and
Linformer [37] in a single head example. In our method, guided by the sparse
connectivity mask $M$, we compute only the nonzero elements of the sparse
full-rank attention matrix $\tilde{A}$. In order to ensure computational
efficiency, we want to have both a sparse up-projection and a sparse low-rank
attention matrix. This is equivalent to reconstructing the sparse attention
matrix $\tilde{A}$ as an affine combination over a set of sparse basis vectors
using a sparse coefficient vector:

$\tilde{A}_{ij}={\text{softmax}\bigg{(}{\frac{QK^{\top}}{\sqrt{d}}}\bigg{)}}_{ij}\quad\textrm{iff}\quad{M}_{ij}=1.$
(4)

Another way of formulating the sparse full-rank attention matrix is as a
sparse element-wise product of the sparse connectivity mask $M$ with the full-
rank attention matrix:

$\tilde{A}=M\odot_{\text{sparse}}A.$ (5)

Here, $\odot_{\text{sparse}}$ is the sparse element-wise product operator,
which skips multiplications by zero. Therefore, computing the sparse full-rank
attention matrix $\tilde{A}$ (Eq. 4) costs only as many FLOPs as there are
nonzero elements in the connectivity mask $M$. In particular, computing the
sparse full-rank attention matrix costs less than the $O(n^{2}d)$ required by
naïve MHSA.

Finally, Sparsifiner computes a sparse attention-value product using the
sparse full-rank attention matrix $\tilde{A}$ and the value matrix $V$:

$X^{l+1}=\tilde{A}V.$ (6)

By computing the sparse full-rank attention matrix $\tilde{A}$ (Eq. 4) guided
by the sparse connectivity mask, and then computing the sparse attention-value
product, we remove the $O(n^{2}d)$ complexity required by the naïve MHSA
operation. Instead, the sparse MHSA operation in Sparsifiner performs a number
of operations proportional to the number of nonzero elements in the
connectivity mask $M$.

Objective functions — The training of Sparsifiner includes training the
attention connectivity predictor modules and fine-tuning the backbone to make
it adapt to sparse attention. We adopt the standard cross-entropy loss:

$\mathcal{L}_{\text{cls}}=\text{CrossEntropy}(\textbf{y}^{\text{pred}},\textbf{y})$
(7)

where $\textbf{y}^{\text{pred}}$ is the predicted class distribution and y is
the ground-truth class distribution.

To minimize the influence on performance of the attention sparsification
process, we use a pre-trained backbone model as a teacher within a knowledge
distillation framework. First, we make the tokens at the last layer close to
the ones of the teacher model, where x and $\textbf{x}^{\text{teach}}$ are the
tokens after the last block of the Sparsifiner and the teacher model,
respectively.

$\mathcal{L}_{\text{distill}}^{\text{token}}=\text{MSE}(\textbf{x},\textbf{x}^{\text{teach}}).$
(8)

Second, we minimize the difference of Sparsifiner and the teacher model’s
predictions via KL divergence:

$\mathcal{L}_{\text{distill}}^{\text{cls}}=\text{KL}(\textbf{y}^{\text{pred}}||\textbf{y}^{\text{teach}}).$
(9)

Third, we want the connectivity score map generated by the connectivity mask
predictor to be a good low-rank approximation of the teacher attention, which
can be viewed as knowledge distillation of the attention map. We minimize the
Euclidean distance between them:

$\mathcal{L}_{\text{distill}}^{\text{attn}}=\text{MSE}(\tilde{A}^{\text{down}}W^{\text{up}},A^{\text{teach}}).$
(10)

Finally, to enforce the sparsity of the up-projection matrix, we use the
$L_{2}$ regularization. We tried $L_{1}$ regularization but found that $L_{2}$
gives better training convergence with sufficient sparsity in practice.

$\mathcal{L}_{\text{spa}}=\sum_{i}(w^{\text{up}}_{i})^{2}$ (11)

The full training objective combines all objectives:

$\mathcal{L}=\mathcal{L}_{\text{cls}}+\lambda_{\text{distill}}^{\text{token}}\mathcal{L}_{\text{distill}}^{\text{token}}+\lambda_{\text{distill}}^{\text{cls}}\mathcal{L}_{\text{distill}}^{\text{cls}}+\lambda_{\text{distill}}^{\text{attn}}\mathcal{L}_{\text{distill}}^{\text{attn}}+\lambda_{\text{spa}}\mathcal{L}_{\text{spa}}$
(12)

Where we set the weight decay as $0.05$ in the optimizer instead of directly
adding $\lambda_{\text{spa}}\mathcal{L}_{\text{spa}}$ to the objective.

Figure 3: Visualization of connectivity mask (b) with sparse (c) and full (d)
attention maps for a given query patch (a). In the heatmaps, the blue darker
color indicates lower, and yellow brighter color indicates higher attention
value. Here we visualize the attention maps for only 3 layers and 4 heads of
the ViT. For the dog image (top) we visualize layers 3–5, while for the bear
image (bottom) we visualize layers 6–8. We observe that in earlier layers the
attention map focuses more on positional information such as nearby tokens,
while in later layers semantic relations with distant tokens are more
important. For each query patch indicated by a yellow square in the input
image, Sparsifiner predicts a sparse connectivity mask using a low-rank
approximation to full attention. Using the sparse connectivity mask,
Sparsifiner efficiently computes a sparse full-rank attention matrix. By
comparison with the rightmost full attention, sparse attention retains all of
the most salient relations with the given query patch, while discarding
redundant or noisy information in the rest of the image.

##  4 Experiments and Results

Implementation details — We train all of the models on the ImageNet dataset
[12]. By default, the connectivity mask predictor module is incorporated into
every layer of DeiT-S [34] and LV-ViT-S [17]. In all of our experiments, we
set the reduced dimension $n_{\text{down}}$ to $32$ and $\tau$ to $0.05$ which
ensures 87% sparsity ratio of the basis coefficient. The attention budget $B$
is in the range $(0,\text{number of tokens}]$. Budget $B$ is directly
determined by the attention keep rate in $(0,1]$ as the ceiling of the keep
rate multiplied by the total number of tokens.

We follow most of the training techniques used in DeiT-S and LV-ViT-S. We use
pre-trained ViT models to initialize the backbone models. To improve speed of
convergence, we propose a two-phase training strategy. In the first phase, we
freeze the backbone model and train the connectivity mask predictor module
with attention distillation loss and L2 regularization only. Specifically, we
set $\lambda_{\text{distill}}^{\text{token}}=0.0$,
$\lambda_{\text{distill}}^{\text{cls}}=0.0$,
$\lambda_{\text{distill}}^{\text{attn}}=1.0$ and we also apply a threshold
1e-2 on basis $W^{\text{up}}$ to ensure 90% sparsity. We found that this
setting helps the connectivity mask predictor to learn $W^{\text{up}}$ quickly
and loss converges within 5 epochs. In the second phase, we jointly train the
backbone model and the connectivity mask predictor module for another 40
epochs. we set $\lambda_{\text{distill}}^{\text{token}}=0.5$,
$\lambda_{\text{distill}}^{\text{cls}}=0.5$,
$\lambda_{\text{distill}}^{\text{attn}}=0.0$. More details can be found in the
supplementary material.

Sparse connectivities and attention visualization — In order to qualitatively
investigate the quality of Sparsifiner’s sparse attention approximation, we
visualize its connectivity mask and sparse reconstructed attention map (Fig.
3). We show the original input image and the connectivity mask of the query
patch, where the dark regions represent tokens that are not attended to by the
query patch token. For each attention head, Sparsifiner generates a
corresponding connectivity mask. We find that the connectivity mask acts as a
region proposal mechanism, which allows different attention heads to locate
different informative tokens and gather diverse semantic information.
Furthermore, we visualize the sparse attention map efficiently generated using
the connectivity mask and compare it with the full attention map. We find that
the sparse attention map retains all of the highest connectivity values, while
discarding lower connectivity values. Hence the visualizations show that
Sparsifiner retains the most salient relations for a given token, while
discarding noisy background relations.

Figure 4:  MHSA computation (FLOPs) and top-1 accuracy trade-offs on ImageNet. We compare Sparsifiner with the state-of-the-art token pruning methods. Sparsifiner achieves superior trade-offs compared to the baseline. We also report MHSA FLOPs and top-1 accuracy for Sparsifiner-S under varying attention keep rate.  Model |  | Tok.
---
keep
rate
| Att.
---
keep
rate
| MHSA
---
(MFLOPs)
| Top-1
---
Acc.
(%)
DeiT-S [34] | $1.0$ | $1.0$ | $357.7$ | $79.8$
EViT [15] | $0.7$ | $1.0$ |  $193.1$ ($-46$%) | $\mathbf{79.5}$
DynamicViT [27] | $0.7$ | $1.0$ |  $193.1$ ($-46$%) | $79.3$
Sparsif-EViT (ours) | $0.7$ | $0.25$ |  $113.3$ ($-68$%) | $\mathbf{79.5}$
Sparsifiner (ours) | $0.7$ | $0.25$ |  $113.3$ ($-68$%) | $79.3$
EViT [15] | $0.5$ | $1.0$ |  $149.1$ ($-58$%) | $78.5$
DynamicViT [27] | $0.5$ | $1.0$ |  $149.1$ ($-58$%) | $77.3$
Sparsif-EViT (ours) | $0.5$ | $0.25$ |  $\mathbf{86.6}$ ($\mathbf{-76}$%) | $78.7$
Sparsifiner (ours) | $0.5$ | $0.25$ |  $\mathbf{86.6}$ ($\mathbf{-76}$%) | $78.4$
LV-ViT-S [17] | $1.0$ | $1.0$ | $476.9$ | $83.3$
EViT-LV-S [15] | $0.7$ | $1.0$ |  $256.0$ ($-46$%) | $83.0$
EViT-LV-S [15] | $0.5$ | $1.0$ |  $198.8$ ($-58$%) | $82.5$
DynViT-LV-S [27] | $0.7$ | $1.0$ |  $256.0$ ($-46$%) | $83.0$
DynViT-LV-S [27] | $0.5$ | $1.0$ |  $198.8$ ($-58$%) | $82.0$
Sparsif-LV-S (ours) | $1.0$ | $0.5$ |  $339.7$ ($-29$%) | $\mathbf{83.4}$
Sparsif-LV-S (ours) | $1.0$ | $0.25$ |  $221.7$ ($-54$%) | $83.3$
Sparsif-LV-S (ours) | $1.0$ | $0.1$ |  $\mathbf{149.5}$ ($\mathbf{-69}$%) | $82.8$
Table 1: Comparison with token pruning methods on DeiT-S [34] and LV-ViT-S
[17] base models. Token pruning methods such as EViT [15] and DynamicViT [27]
prune tokens at fixed layers. We show that token pruning methods combine with
Sparsifiner’s sparse attention connectivities to produce a complementary
effect. Sparsifiner combined with EViT [15] achieves a $68$% reduction in
FLOPs compared with the DeiT-S [34] baseline, while maintaining a top-1
accuracy of $79.5$%. Hence Sparsifiner achieves the same top-1 accuracy as
EViT [15] with significantly better MHSA FLOPs reduction. The input resolution
is $224\times 224$.

Comparison with token pruning — We train and evaluate Sparsifiner on ImageNet
and compare to state-of-the-art token pruning baselines (Tab. 1). Since our
research question addresses the problem of reducing MHSA complexity, we report
trade-offs between top-1 accuracy on ImageNet and computation in terms of MHSA
FLOPs. We compare Sparsifiner against baselines by adjusting two
hyperparameters: token and attention keep rate. The token keep rate is the
fraction of tokens kept in the network at predetermined layers where pruning
occurs, which we set according to established token pruning baselines [15,
27]. The attention keep rate is the fraction of attention connectivities at
any given MHSA layer, as determined by the connectivity mask predictor (Eq.
3). Hence, varying the attention keep rate reduces FLOPs without necessitating
removal of tokens as in token pruning. But both techniques can be combined to
achieve complementary effects.

To provide a variety of comparisons we experiment with adding token pruning
and Sparsifiner to two common baseline ViT models: DeiT [34] and LV-ViT [17].
On both models, Sparsifiner achieves significant computation saving while
maintaining a relatively modest drop in top-1 accuracy. For example, LV-ViT-S
[17] trained with Sparsifiner with an attention keep rate of $0.25$ reduces
the MHSA FLOPs by $53.5$% while maintaining the top-1 accuracy of the baseline
LV-ViT-S model on ImageNet. When used in combination with token pruning,
Sparsifiner achieves an even superior reduction in MHSA FLOPs while
maintaining comparable top-1 accuracy to EViT, and superior top-1 accuracy to
DynamicViT.

Att. keep rate | Att. num. |  | MHSA
---
(MFLOPs)
| Top-1
---
Acc (%)
$1.0$ (DeiT-S [34]) | $197$ | $357.7$ | $79.82$
$0.9$ | $178$ | $396.8$ | $80.02$
$0.8$ | $158$ | $360.6$ | $79.97$
$0.7$ | $138$ |  $324.6$ ($-9$%) | $79.96$
$0.6$ | $119$ |  $290.3$ ($-19$%) | $79.98$
$0.5$ | $99$ |  $254.2$ ($-29$%) | $79.94$
$0.4$ | $79$ |  $218.0$ ($-39$%) | $79.92$
$0.3$ | $60$ |  $183.6$ ($-49$%) | $79.83$
$0.2$ | $40$ |  $147.5$ ($-59$%) | $79.71$
$0.1$ | $20$ |  $111.4$ ($-69$%) | $79.42$
$0.05$ | $10$ |  $93.3$ ($-74$%) | $78.75$
$0.01$ | $2$ |  $78.9$ ($-78$%) | $73.03$
Table 2: Effect of attention budget on FLOPs and top-1 accuracy. Here the
“keep rate” refers to the number of attention connectivities retained at each
layer. All other attention connectivities in the sparse full-rank attention
matrix (Eq. 4) are set to zero. When keeping only $10$ attention
connectivities, Sparsifiner produces a top-1 accuracy reduced by only $1.0$%
compared to the full-attention baseline DeiT-S [34], but with a $73.9$%
reduction in FLOPs. The input resolution is $224\times 224$.

Varying MHSA attention budget — We varied the attention budget of MHSA in
order to investigate the tradeoff between MHSA FLOPs and top-1 accuracy for
Sparsifiner-S (Tab. 2). The results evaluated on ImageNet show that
Sparsifiner-S produces a superior Pareto frontier compared with previous
approaches (Fig. 4). In particular, Sparsifiner-S models with attention
budgets of $40$ and above achieved top-1 accuracy within $0.1$% of the full-
rank DeiT-S [34] model, while using $58.8$% fewer FLOPs in MHSA. Furthermore,
Sparsifiner-S models with high attention budgets of $79$ and above achieved
superior top-1 accuracy compared with the full-rank DeiT-S [34] model, while
using fewer FLOPs in MHSA. This suggests that Sparsifiner’s sparse full-rank
attention reconstruction mechanism induces a useful regularization effect that
improves model generalization.

Model |  | Att.
---
keep
rate
| MHSA
---
(MFLOPs)
| Overall
---
(GFLOPs)
| Top-1
---
Acc
(%)
DeiT-T | $1.0$ | $1534.1$ | $3.58$ | $75.45$
Sparsifiner-T | $0.5$ |  $851.0$ ($-45$%) |  $2.89$ ($-19$%) | $75.45$
Sparsifiner-T | $0.25$ |  $452.9$ ($-70$%) |  $2.49$ ($-30$%) | $75.35$
Sparsifiner-T | $0.1$ |  $240.5$ ($-84$%) |  $2.28$ ($-36$%) | $74.58$
Table 3: Results on high resolution $384\times 384$ images. We apply
Sparsifiner on DeiT-T [34] with resolution 384. We show that Sparsifiner
reduce the MHSA complexity of DeiT-T-384 [34] by over $84$% with modest
accuracy drop. Since the number of tokens is quadratic in the resolution,
Sparsifiner can reduce a larger portion of MHSA complexity on high-resolution
images.

Accelerating ViT on high-resolution images — To show the effectiveness of our
method on larger input size, we apply our method to DeiT-T [34] with
$384\times 384$ resolution (Tab. 3). When dealing with high-resolution images,
due to quadratic complexity in the number of tokens, MHSA becomes increasingly
expensive compared to the feedforward operations. We reduce the MHSA
complexity of the DeiT-T [34] model with $384\times 384$ input by over $80$%
with less than $1$% accuracy drop. Our method shows a great potential to
accelerate ViT on even higher resolution images where token quantity dominates
the model complexity.

Model | MHSA (MFLOPs) | Top-1 Acc (%)
---|---|---
Linformer [37] | $246.73$ | 77.54
Sparsifiner-S (ours) | $224.04$ | 79.79
Table 4: Comparison of sparse full-attention reconstruction with low-rank
attention reconstruction. Sparsifiner-S achieves a $2.1$% absolute percentage
point improvement in top-1 accuracy compared with Linformer [37].

(a) Query in input image

(b) Full attention (naïve MHSA)

(c) Low-rank attention (Linformer)

(d) Full-rank sparse att. (Sparsifiner)

Figure 5: Low-rank attention (Linformer) and full-rank sparse attention
(Sparsifiner) heatmaps. For a given query patch indicated by a yellow square
(a), we visualize its low-rank attention map (Linformer) (c) and full-rank
sparse attention map (Sparsifiner) (d). Due to discarding the long tail of the
attention matrix’s eigenspectrum, low-rank attention produces a coarse
attention map. By contrast, full-rank sparse attention bears closer
resemblance to full attention (b) with low-salience connectivities discarded.
Figure 6: Visualization of the up-projection matrix $W^{\text{up}}$ of the
first $6$ layers of Sparsifiner-S, which we refer to here as a sparse basis.
We visualize $24$ dimensions of the sparse basis. Dark blue weights indicate
low values, which are pruned after training so that only the bright yellow
weights are left over. Qualitatively, the sparse basis has a high level of
sparsity, making sparse attention reconstruction efficient. Figure 7:
Visualization of the sparse basis coefficient of the $5$th attention head over
$12$ layers of Sparsifiner-S. Dark blue regions indicate low values that are
pruned before sparse attention reconstruction during inference, leaving only
bright yellow coefficients.

Low-rank: connectivities or attention? — Our approach raises a research
question: does the utility of the dense low-rank attention matrix come from
its use as a connectivity mask? Or is it sufficient to directly use the dense
low-rank attention matrix, foregoing the need to reconstruct the sparse full-
rank attention matrix, i.e., the Linformer [37] approach? We answered this
question by comparing the top-1 accuracy of the two approaches (Tab. 4). In
this experiment, Sparsifiner-S and Linformer [37] were trained under identical
settings, differing only in the attention approximation method. Sparsifiner-S
uses a reconstructed sparse full-rank attention matrix, while Linformer uses
the dense low-rank attention matrix directly. In order to give both models
similar representational capacity, we set the low-rank dimension of Linformer
[37] equal to the sparse attention budget of Sparsifiner-S. This enforces that
the attention-value product of both models’ MHSA has the same complexity.

Using the sparse full-rank attention matrix produces a $2.1$% absolute
percentage point improvement in top-1 accuracy compared with Linformer. This
improvement reinforces the superiority of using the low-rank query-key product
as a connectivity mask, rather than using the low-rank attention matrix
directly. Using the low-rank attention matrix to directly compute the
attention-value product with a down-projected value discards the long tail of
the full attention matrix’s eigenspectrum [37]. In contrast, using the low-
rank query-key product as a connectivity mask reduces computation by a
different mechanism. By using a low-rank connectivity mask to produce a sparse
full-rank attention matrix, the long-tail of the full attention matrix’s
eigenspectrum is preserved. Based on the significant improvement in top-1
accuracy, we conclude that these long-tail eigenvalues are important for model
predictive quality in ViTs.

Low- and full-rank attention visualization — In order to further illuminate
the qualitative difference between low- and full-rank attention in ViTs, we
also present the masked attention heatmap and the full attention heatmap of
the query patch (Fig. 5). We show that a connectivity mask can accurately
preserve key tokens that are highly related to the query patch and remove the
irrelevant ones. As a result, the masked attention heatmap preserves structure
and discards noise compared with the full attention heatmap. The visualization
results also validate that our Sparsifiner can effectively approximate the
full attention ViT.

Sparse low-rank basis and up-projection matrix visualization — To demonstrate
that the connectivity mask can be computed by sparse-sparse matrix
multiplication, we visualize the up-projection matrix $W^{\text{up}}$ of the
first six layers of Sparsifiner (Fig. 6). Because the reconstructed sparse
attention matrix is a combination of the up-projection matrix’s weights, we
refer to it as a sparse basis. We show that Sparsifiner naturally learns a
sparse basis of local regions resembling 2D Gaussians. For a given token, the
sparse bases corresponding to object locations with salient semantic and/or
spatial information will activate. Since the sparse attention reconstruction
(Eq. 5) is a product of the sparse low-rank attention matrix with the up-
projection matrix, we also visualize the post-softmax low-rank attention
matrix. Here we view the low-rank attention matrix as a sparse coefficient of
the sparse basis (Fig. 7). Qualitatively, the sparse coefficient also exhibits
a high degree of sparsity, further validating the efficiency of the sparse
attention reconstruction via sparse-sparse matrix multiplication.

##  5 Conclusions

We presented a novel computationally efficient approach to learn unstructured,
instance-dependent attention in ViTs. The development of sparse attention
mechanisms such as Sparsifiner opens the door to further research into
accelerating sparse ViTs using software-hardware systems approaches.
Sparsifiner shows the promise of sparse attention for scaling ViTs to larger
and more complex vision tasks. But software-hardware systems approaches are
needed to realize its full potential. We hope that our work inspires further
research at the intersection of sparse algorithms for ViTs and software-
hardware systems approaches to support those sparse algorithms.

## References

  * [1] Iz Beltagy, Matthew E Peters, and Arman Cohan.  Longformer: The long-document transformer.  arXiv preprint arXiv:2004.05150, 2020.
  * [2] Gedas Bertasius, Heng Wang, and Lorenzo Torresani.  Is space-time attention all you need for video understanding?  In ICML, volume 2, page 4, 2021.
  * [3] Nicolas Carion, Francisco Massa, Gabriel Synnaeve, Nicolas Usunier, Alexander Kirillov, and Sergey Zagoruyko.  End-to-End Object Detection with Transformers.  In ECCV, 2020.
  * [4] Nicolas Carion, Francisco Massa, Gabriel Synnaeve, Nicolas Usunier, Alexander Kirillov, and Sergey Zagoruyko.  End-to-end object detection with transformers.  In European conference on computer vision, pages 213–229. Springer, 2020.
  * [5] Mark Chen, Alec Radford, Rewon Child, Jeffrey Wu, Heewoo Jun, David Luan, and Ilya Sutskever.  Generative pretraining from pixels.  In International conference on machine learning, pages 1691–1703. PMLR, 2020.
  * [6] Bowen Cheng, Ishan Misra, Alexander G. Schwing, Alexander Kirillov, and Rohit Girdhar.  Masked-attention mask transformer for universal image segmentation.  2022\.
  * [7] Bowen Cheng, Alexander G. Schwing, and Alexander Kirillov.  Per-pixel classification is not all you need for semantic segmentation.  2021\.
  * [8] Rewon Child, Scott Gray, Alec Radford, and Ilya Sutskever.  Generating long sequences with sparse transformers.  In arXiv:1904.10509, 2019.
  * [9] Krzysztof Marcin Choromanski, Valerii Likhosherstov, David Dohan, Xingyou Song, Andreea Gane, Tamas Sarlos, Peter Hawkins, Jared Quincy Davis, Afroz Mohiuddin, Lukasz Kaiser, David Benjamin Belanger, Lucy J Colwell, and Adrian Weller.  Rethinking attention with performers.  In ICLR, 2021.
  * [10] Xiangxiang Chu, Zhi Tian, Yuqing Wang, Bo Zhang, Haibing Ren, Xiaolin Wei, Huaxia Xia, and Chunhua Shen.  Twins: Revisiting the design of spatial attention in vision transformers.  Advances in Neural Information Processing Systems, 34:9355–9366, 2021.
  * [11] Zhigang Dai, Bolun Cai, Yugeng Lin, and Junying Chen.  Up-detr: Unsupervised pre-training for object detection with transformers.  In Proceedings of the IEEE/CVF conference on computer vision and pattern recognition, pages 1601–1610, 2021.
  * [12] Jia Deng, Wei Dong, Richard Socher, Li-Jia Li, Kai Li, and Li Fei-Fei.  Imagenet: A Large-scale Hierarchical Image Database.  In CVPR, 2009.
  * [13] 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 ICLR, 2021.
  * [14] Brendan Duke, Abdalla Ahmed, Christian Wolf, Parham Aarabi, and Graham W. Taylor.  SSTVOS: Sparse Spatiotemporal Transformers for Video Object Segmentation.  In CVPR, 2021.
  * [15] Qihua Feng, Peiya Li, Zhixun Lu, Chaozhuo Li, Zefang Wang, Zhiquan Liu, Chunhui Duan, and Feiran Huang.  Evit: Privacy-preserving image retrieval via encrypted vision transformer in cloud computing.  arXiv preprint arXiv:2208.14657, 2022.
  * [16] Jonathan Ho, Nal Kalchbrenner, Dirk Weissenborn, and Tim Salimans.  Axial attention in multidimensional transformers.  arXiv preprint arXiv:1912.12180, 2019.
  * [17] Zi-Hang Jiang, Qibin Hou, Li Yuan, Daquan Zhou, Yujun Shi, Xiaojie Jin, Anran Wang, and Jiashi Feng.  All tokens matter: Token labeling for training better vision transformers.  Advances in Neural Information Processing Systems, 34:18590–18602, 2021.
  * [18] Angelos Katharopoulos, Apoorv Vyas, Nikolaos Pappas, and François Fleuret.  Transformers are rnns: Fast autoregressive transformers with linear attention.  In International Conference on Machine Learning, pages 5156–5165. PMLR, 2020.
  * [19] Nikita Kitaev, Lukasz Kaiser, and Anselm Levskaya.  Reformer: The efficient transformer.  In International Conference on Learning Representations, 2020.
  * [20] Juho Lee, Yoonho Lee, Jungtaek Kim, Adam Kosiorek, Seungjin Choi, and Yee Whye Teh.  Set transformer: A framework for attention-based permutation-invariant neural networks.  In International conference on machine learning, pages 3744–3753. PMLR, 2019.
  * [21] Ze Liu, Han Hu, Yutong Lin, Zhuliang Yao, Zhenda Xie, Yixuan Wei, Jia Ning, Yue Cao, Zheng Zhang, Li Dong, Furu Wei, and Baining Guo.  Swin transformer v2: Scaling up capacity and resolution.  In CVPR, 2022.
  * [22] 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 ICCV, 2021.
  * [23] Niki Parmar, Ashish Vaswani, Jakob Uszkoreit, Lukasz Kaiser, Noam Shazeer, Alexander Ku, and Dustin Tran.  Image transformer.  In International conference on machine learning, pages 4055–4064. PMLR, 2018.
  * [24] Hao Peng, Nikolaos Pappas, Dani Yogatama, Roy Schwartz, Noah Smith, and Lingpeng Kong.  Random feature attention.  In International Conference on Learning Representations, 2021.
  * [25] Jiezhong Qiu, Hao Ma, Omer Levy, Wen-tau Yih, Sinong Wang, and Jie Tang.  Blockwise self-attention for long document understanding.  In Findings of the Association for Computational Linguistics: EMNLP 2020, pages 2555–2565, Online, Nov. 2020. Association for Computational Linguistics.
  * [26] Jack W. Rae, Anna Potapenko, Siddhant M. Jayakumar, Chloe Hillier, and Timothy P. Lillicrap.  Compressive transformers for long-range sequence modelling.  In International Conference on Learning Representations, 2020.
  * [27] Yongming Rao, Wenliang Zhao, Benlin Liu, Jiwen Lu, Jie Zhou, and Cho-Jui Hsieh.  DynamicViT: Efficient Vision Transformers with Dynamic Token Sparsification.  In Advances in Neural Information Processing Systems (NeurIPS), 2021\.
  * [28] Cedric Renggli, André Susano Pinto, Neil Houlsby, Basil Mustafa, Joan Puigcerver, and Carlos Riquelme.  Learning to merge tokens in vision transformers.  arXiv preprint arXiv:2202.12015, 2022.
  * [29] Aurko Roy, Mohammad Saffar, Ashish Vaswani, and David Grangier.  Efficient content-based sparse attention with routing transformers.  Transactions of the Association for Computational Linguistics, 9:53–68, 2021.
  * [30] Michael Ryoo, AJ Piergiovanni, Anurag Arnab, Mostafa Dehghani, and Anelia Angelova.  TokenLearner: Adaptive Space-Time Tokenization for Videos.  In NeurIPS, 2021.
  * [31] Yehui Tang, Kai Han, Yunhe Wang, Chang Xu, Jianyuan Guo, Chao Xu, and Dacheng Tao.  Patch slimming for efficient vision transformers.  In CVPR, 2022.
  * [32] Yehui Tang, Kai Han, Yunhe Wang, Chang Xu, Jianyuan Guo, Chao Xu, and Dacheng Tao.  Patch slimming for efficient vision transformers.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 12165–12174, 2022.
  * [33] Yi Tay, Dara Bahri, Liu Yang, Donald Metzler, and Da-Cheng Juan.  Sparse sinkhorn attention.  In International Conference on Machine Learning, pages 9438–9447. PMLR, 2020.
  * [34] Hugo Touvron, Matthieu Cord, Matthijs Douze, Francisco Massa, Alexandre Sablayrolles, and Herve Jegou.  Training Data-efficient Image Transformers & Distillation through Attention.  In ICML, 2021.
  * [35] Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Ł ukasz Kaiser, and Illia Polosukhin.  Attention is all you need.  In NeurIPS. 2017.
  * [36] Elena Voita, David Talbot, Fedor Moiseev, Rico Sennrich, and Ivan Titov.  Analyzing multi-head self-attention: Specialized heads do the heavy lifting, the rest can be pruned.  In ACL, 2019.
  * [37] Sinong Wang, Belinda Z Li, Madian Khabsa, Han Fang, and Hao Ma.  Linformer: Self-attention with linear complexity.  arXiv preprint arXiv:2006.04768, 2020.
  * [38] Wenhai Wang, Enze Xie, Xiang Li, Deng-Ping Fan, Kaitao Song, Ding Liang, Tong Lu, Ping Luo, and Ling Shao.  Pyramid vision transformer: A versatile backbone for dense prediction without convolutions.  In Proceedings of the IEEE/CVF International Conference on Computer Vision, pages 568–578, 2021.
  * [39] Li Yuan, Yunpeng Chen, Tao Wang, Weihao Yu, Yujun Shi, Zi-Hang Jiang, Francis EH Tay, Jiashi Feng, and Shuicheng Yan.  Tokens-to-token vit: Training vision transformers from scratch on imagenet.  In Proceedings of the IEEE/CVF International Conference on Computer Vision, pages 558–567, 2021.
  * [40] Manzil Zaheer, Guru Guruganesh, Kumar Avinava Dubey, Joshua Ainslie, Chris Alberti, Santiago Ontanon, Philip Pham, Anirudh Ravula, Qifan Wang, Li Yang, et al.  Big Bird: Transformers for Longer Sequences.  In NeurIPS, 2020.
  * [41] Wang Zeng, Sheng Jin, Wentao Liu, Chen Qian, Ping Luo, Wanli Ouyang, and Xiaogang Wang.  Not all tokens are equal: Human-centric visual analysis via token clustering transformer.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 11101–11111, 2022.
  * [42] Yanhong Zeng, Jianlong Fu, and Hongyang Chao.  Learning joint spatial-temporal transformations for video inpainting.  In European Conference on Computer Vision, pages 528–543. Springer, 2020.
  * [43] Pengchuan Zhang, Xiyang Dai, Jianwei Yang, Bin Xiao, Lu Yuan, Lei Zhang, and Jianfeng Gao.  Multi-scale vision longformer: A new vision transformer for high-resolution image encoding.  In Proceedings of the IEEE/CVF International Conference on Computer Vision, pages 2998–3008, 2021.
  * [44] Minghang Zheng, Peng Gao, Renrui Zhang, Kunchang Li, Xiaogang Wang, Hongsheng Li, and Hao Dong.  End-to-end object detection with adaptive clustering transformer.  2021\.
  * [45] Luowei Zhou, Yingbo Zhou, Jason J Corso, Richard Socher, and Caiming Xiong.  End-to-end dense video captioning with masked transformer.  In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 8739–8748, 2018.
  * [46] Xizhou Zhu, Weijie Su, Lewei Lu, Bin Li, Xiaogang Wang, and Jifeng Dai.  Deformable {detr}: Deformable transformers for end-to-end object detection.  In International Conference on Learning Representations, 2021.


# Spiralling branes and $R$-matrices

Yegor Zenkevich 111On leave from ITMP MSU.
Departments of Mathematics, University of California, Berkeley, USA
<EMAIL_ADDRESS>
###### Abstract

We extend the dictionary between Type IIB branes and representations of the
Ding-Iohara-Miki (DIM) algebra to the case when one of the space directions is
a circle. It is well-known that the worldvolume theory on branes wrapping the
circle is a $5d$ $\mathcal{N}=1$ gauge theory with adjoint matter, or more
generally of cyclic quiver type, and the corresponding intertwiners of the DIM
algebra give their Nekrasov partition functions. However, we find that there
exists a much wider natural class of intertwiners corresponding to branes
spiralling around the compactified direction, with many interesting
properties. We consider two examples, one corresponding to a spiralling D5
brane and another to a D3 brane. The former gives rise to the $K$-theoretic
vertex function counting sheaves on $\mathbb{C}^{3}$ while the latter produces
the ‘‘non-stationary elliptic Ruijsenaars wavefunctions’’ introduced recently
by Shiraishi.

To T.

##  1 Introduction

String theory branes can be understood on several levels. Historically they
were first introduced as boundary conditions for open strings in which case
they can be thought of as submanifolds of the ambient (or bulk) space, e.g.
$\mathbb{R}^{10}$. However, this plain geometric description becomes
inadequate if a stack of $N>1$ branes spanning the same submanifold is
considered. Then, somewhat akin to Heisenberg’s development of quantum
mechanics from the classical picture, the coordinates normal to the branes
become matrices acting in an $N$-dimensional vector space (the Chan-Paton
space) [1]. Reformulated more mathematically, a stack of branes becomes a rank
$N$ vector bundle on a submanifold of the bulk space. Naturally, the bundle
may be topologically nontrivial and thus some stacks of branes wrapping the
same submanifold may be nonequivalent.

More generally, one would like to consider the possibility of antibranes, i.e.
the objects which upon being added to the system ‘‘cancel’’ (annihilate)
branes of a given type. Since there are nonequivalent stacks of branes that
may live on the same submanifolds one can ask what happens if one tries to
annihilate a pair of such inequivalent stacks. The result turns out to be a
stack of branes on a sub-submanifold, in general of a smaller dimension. The
mathematical formalism to consider branes of different dimension on equal
footing is provided by coherent sheaves on the bulk space [2]. Vector bundles
on submanifolds of the bulk space are examples of coherent sheaves, however
the sheaf approach is more general. The essence of it is to understand vector
bundles as modules over the ring of functions on the bulk space. Indeed, if
$v(x)$ is a (local) section of a bundle $\mathcal{E}$ then $f(x)v(x)$ is too
for every function $f(x)$ on the bulk space. Adding non-interacting branes to
the system corresponds to taking the direct sum of sheaves while the
annihilation is captured by introducing equivalence relation which allows one
to consider complexes of sheaves.

The overall picture with modules over a ring, sums and complexes thereof begs
for a representation theoretic description. It does arise on a more refined
level when one considers _bound states_ of branes. The representation space is
interpreted as the Hilbert space of (BPS) bound states of a ‘‘heavy’’ brane
with a number of ‘‘light’’ branes. The algebras rising in this way are called
the BPS algebras [3]. Pairs of ‘‘heavy’’ branes correspond to tensor products
of representations.

The BPS algebras arise in different string theories and in different
backgrounds. Here we will be interested in a particular case [4] in which
branes are of Type IIB string theory and the algebra is the Ding-Iohara-Miki
(DIM) algebra [5]222More generally, also of other quantum toroidal algebras
[6] and affine Yangians [7], [8].. In this approach 3- and 5-branes correspond
to two different types of DIM algebra representations, collections of non-
interacting branes are tensor products of representations and brane junctions
are intertwining operators between ingoing and outgoing collections of branes.
Also, brane _crossings_ (when one brane passes behind another without merging)
correspond to DIM $R$-matrices taken in the appropriate representations. The
details about the DIM algebra, its representations and some of the
intertwining operators can be found e.g. in the Appendices to [4], [12] and
[23].

To make the correspondence more precise in the table below we list the main
types of branes and representations we are going to consider.

$\begin{array}[]{l|l|ccc|cc|c|c}&&&&&\lx@intercol\hfil\text{picture}\hfil\lx@intercol\vrule\lx@intercol&\tau&\\\
\text{Brane}&\text{DIM
rep}&{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\mathbb{C}_{q}}&{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}\mathbb{C}_{t^{-1}}}&{\color[rgb]{.5,0,.5}\definecolor[named]{pgfstrokecolor}{rgb}{.5,0,.5}\mathbb{C}_{t/q}}&\mathbb{R}_{x}&S^{1}_{y}&\mathbb{R}_{\tau}&S^{1}_{10}\\\
\hline\cr{\color[rgb]{.5,0,.5}\definecolor[named]{pgfstrokecolor}{rgb}{.5,0,.5}\mathrm{D5}_{q,t^{-1}}}&{\color[rgb]{.5,0,.5}\definecolor[named]{pgfstrokecolor}{rgb}{.5,0,.5}\mathcal{F}^{(0,1)}_{q,t^{-1}}}&\--&\--&&&-&&-\\\
{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}\mathrm{D5}_{q,t/q}}&{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}\mathcal{F}^{(0,1)}_{q,t/q}}&\--&&\--&&-&&-\\\
{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\mathrm{D5}_{t^{-1},t/q}}&{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\mathcal{F}^{(0,1)}_{t^{-1},t/q}}&&\--&\--&&-&&-\\\
\hline\cr{\color[rgb]{.5,0,.5}\definecolor[named]{pgfstrokecolor}{rgb}{.5,0,.5}\mathrm{NS5}_{q,t^{-1}}}&{\color[rgb]{.5,0,.5}\definecolor[named]{pgfstrokecolor}{rgb}{.5,0,.5}\mathcal{F}^{(1,0)}_{q,t^{-1}}}&\--&\--&&-&&&-\\\
{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}\mathrm{NS5}_{q,t/q}}&{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}\mathcal{F}^{(1,0)}_{q,t/q}}&\--&&\--&-&&&-\\\
{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\mathrm{NS5}_{t^{-1},t/q}}&{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\mathcal{F}^{(1,0)}_{t^{-1},t/q}}&&\--&\--&-&&&-\\\
\hline\cr{\color[rgb]{.5,0,.5}\definecolor[named]{pgfstrokecolor}{rgb}{.5,0,.5}\mathrm{D3}_{t/q}}&{\color[rgb]{.5,0,.5}\definecolor[named]{pgfstrokecolor}{rgb}{.5,0,.5}\mathcal{V}_{t/q}}&&&\--&&&-&-\\\
{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}\mathrm{D3}_{t^{-1}}}&{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}\mathcal{V}_{t^{-1}}}&&\--&&&&-&-\\\
{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\mathrm{D3}_{q}}&{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\mathcal{V}_{q}}&\--&&&&&-&-\\\
\end{array}$ (1)

In the setup above we consider branes on
$\mathbb{C}^{3}\times\mathbb{R}^{2}\times S^{1}\times S^{1}$ and we have
turned on the $\Omega$-background along the three $\mathbb{C}$ planes, its
parameters being $q$, $t^{-1}$ and $t/q$ respectively. The ‘‘picture’’ label
indicates what directions we are going to draw in all of the figures that
follow. In our previous studies [4, 6, 11, 12] the ‘‘picture’’ directions have
been a plane $\mathbb{R}_{x}\times\mathbb{R}_{y}$, but in the present short
note it is essential that it is a cylinder
$\mathbb{R}_{x}\tilde{\times}S^{1}_{y}$ with $S^{1}_{y}$ of radius
$|\ln\Lambda|$. The tilde is meant to indicate that the cylinder has a
nontrivial monodromy (is ‘‘twisted’’), i.e. when $y$ goes to $\Lambda y$ the
coordinate $x$ goes to $\mu x$ (we use multiplicative notation, i.e. all the
pictures are drawn in $(|\ln x|,|\ln y|)$ coordinates333The coordinates $x$
and $y$ here are thought of as complexified by the $U(1)$ Wilson and ’t Hooft
lines around $S^{1}_{10}$ of the gauge field living on each brane.).

The 5-branes of Type IIB string theory are labelled by $(p,q)$-charges with
$(0,1)$ being the D5 brane and $(1,0)$ the NS5 brane. General $(p,q)$-charges
can be thought of as arising from bound states of several D5 and NS5 branes.
The directions of the branes in the ‘‘picture’’ cylinder are dictated by their
$(p,q)$-charges due to supersymmetry. 5-branes span two out of three
$\mathbb{C}$-planes along which the equivariant action ($\Omega$-background)
is turned on. Hence, for every $(p,q)$ charge there are three types of
5-branes: spanning $\mathbb{C}_{q}\times\mathbb{C}_{t^{-1}}$,
$\mathbb{C}_{q}\times\mathbb{C}_{t/q}$ and
$\mathbb{C}_{t^{-1}}\times\mathbb{C}_{t/q}$. These are labelled by the lower
indices and also by color: violet, red and blue respectively. The
representations corresponding to 5-branes are Fock representations e.g.
$\mathcal{F}^{(1,0)}_{q,t^{-1}}(u)$ [10], i.e. spaces generated by the action
of commuting creation operators $a_{-n}$ ($n\in\mathbb{N}$) from the vacuum
state $|\varnothing,u\rangle$. The spectral parameter
$u\in\mathbb{C}^{\times}$ of the representation indicates the position of the
5-brane on the picture cylinder444The argument of the complex parameter $u$ is
provided by the Wilson line around $S^{1}_{10}$ of the $U(1)$ gauge field
living on the brane.. The upper indices of $\mathcal{F}$ represent
$(p,q)$-charge of the brane while the lower ones indicate the pair of
$\mathbb{C}$-planes it spans. 5-branes of the same color sitting at the same
value of $\tau$ (the coordinate along $\mathbb{R}_{\tau}$) can have a triple
junction, while the corresponding Fock representations can be joined using an
intertwining operator (the analogue of an invariant tensor for the DIM
algebra). This leads to the refined topological vertex [9] and $(p,q)$-brane
webs [10].

D3 branes span a single $\mathbb{C}$-plane and therefore are labelled by a
single index and the corresponding color $q$ (blue), $t^{-1}$ (red) or $t/q$
(violet). Classically a D3 brane spans $\mathbb{R}_{\tau}$ and lives at a
point in the picture cylinder. However, with equivariant deformation turned on
the coordinates of the D3 brane in the picture space become non-commutative.
Hence, it does not have a well-defined position $(x,y)\in\mathbb{R}_{x}\times
S^{1}_{y}$ but instead a wavefunction depending either on $x$ or on $y$ or
some combination thereof555In more mathematical terms the wavefunctions should
be a function on a Lagrangian submanifold of $\mathbb{R}_{x}\times S^{1}_{y}$
with respect to the symplectic form $\frac{dx}{x}\wedge\frac{dy}{y}$.. In the
current short note we are going to write everything in the basis of D3 brane
wavefunctions with definite $x$ coordinate and draw the D3 branes as vertical
dashed lines at fixed values of $x$. D3 branes do not have $(p,q)$-charges and
therefore do not change the direction of 5-branes upon joining them. The
corresponding DIM representations are called vector representations
$\mathcal{V}$ and they can be thought of as representations on the space of
functions of $x$. We denote the basis states of the representation
$\mathcal{V}$ by $|w\rangle=\delta\left(\frac{x}{w}\right)$. In fact the only
states appearing in $\mathcal{V}_{q}$ are of the form $|q^{n}w\rangle$ with
$n\in\mathbb{Z}$.

Branes can join together or pass behind each other in the plane of the
picture. Correspondingly DIM algebra representations can be glued using an
intertwiner or can be exchanged using an $R$-matrix. Many of these
possibilities were explored in [4, 6, 10, 11, 12]. In the present short note
we clarify how the dictionary between branes and representations works when
the picture space becomes a cylinder. All local objects like brane junctions
and crossings remain the same but the global structure is different which, as
we will see, leads to interesting effects and novel expressions for the
intertwiners.

Since the picture space is a cylinder, the branes can wrap around it. Here we
need to be careful because of the twist of the cylinder. For example in
general it is not possible to wrap an isolated D5 brane around $S^{1}_{y}$
since its $x$ coordinate will change to $\mu x$ after passing around the
circle. If $\mu$ is nontrivial one needs extra branes with which the D5 would
interact in order to glue the two ends of it. An example of such a picture is
given below. Wavy lines henceforth indicate the identification of the branes
passing through them — notice that pairs of corresponding wavy lines are
shifted with respect to each other.

(2)

In Eq. (2) the ends of the two D5 branes are shifted because of the
interaction with an NS5 brane. The gauge theory engineered by this setup is
the $5d$ $\mathcal{N}=1$ $U(2)$ theory with an extra adjoint field.

In DIM representation theory compactification of the $y$ direction is normally
interpreted as taking the _trace_ over the representations corresponding to
branes wrapping the circle. For example, in Eq. (2) one needs to take a trace
over
$\mathcal{F}^{(0,1)}_{q,t^{-1}}(w_{1})\otimes\mathcal{F}^{(0,1)}_{q,t^{-1}}(w_{2})$.
The twist $\mu$ and the radius of the (complexified exponentiated)
circumference of the circle $\Lambda$ are incorporated as the fugacities
corresponding to the two gradings $d$ and $d_{\perp}$ on the DIM algebra
(again we invite the reader to consult the Appendices of [4] and [11] for
notations), so that the relevant intertwiner has the form

$\mathop{\mathrm{Tr}}\nolimits_{\mathcal{F}^{(0,1)}_{q,t^{-1}}(w_{1})\otimes\mathcal{F}^{(0,1)}_{q,t^{-1}}(w_{2})}\Lambda^{d}\mu^{d_{\perp}}\left(\ldots\right),$
(3)

where $(\ldots)$ denote the interactions with the NS5 brane.

The crucial observation is that there are more general brane configurations on
the cylinder satisfying the conditions of supersymmetry and corresponding to
interesting operators in DIM representation theory. Those appear when a
vertical brane goes full circle around $S^{1}_{y}$ but _does not_ return to
the same $x$ position. Then the brane can continue to the next circle and so
on, possibly for an infinite number of wrappings. We call such configurations
spiralling branes. Algebraically these are _not traces_ of the combinations of
intertwiners ‘‘along the compactification direction’’, at least not traces of
any finite number of them. Nevertheless the resulting expressions are
covariant with respect to DIM transformations, and this fact ensures their
nice properties.

In this short letter we provide two examples of configurations involving
spiralling branes.

  1. 1.

The first setup is a D5q,t/q brane spiralling around $S^{1}_{y}$ _crossing_ an
NS5${}_{q,t^{-1}}$ brane (see Fig. 1). We will find that the matrix element of
the intertwining operator corresponding to Fig. 1 is given by the
$K$-theoretic vertex function [13, 14] counting sheaves on $\mathbb{C}^{3}$.

  2. 2.

The second setup is a stack of $N$ D3q brane spiralling and eventually joining
a stack of $N$ NS5${}_{q,t^{-1}}$ branes as shown in Fig. 2. The resulting
operator turns out to reproduce the screened vertex operator introduced by
Shiraishi in [15, 16] (see also [18]). Let us note that for _specific_ choice
of deformation parameters the screened vertex operator has been obtained in
[17]. This choice corresponds to the case when the D3 brane spiral becomes
tighter and tighter essentially collapsing into a circle (the situation is
slightly more complicated, as we discuss in sec. 5, but the main idea is
true).

These two examples are meant to demonstrate the usefulness of the novel
concept of spiralling branes. It is already clear that many more applications
can be explored. Also the physical meaning of the spiralling does not seem to
be completely understood; this will be explored elsewhere.

The rest of the paper is organized as follows. In sec. 2 we remind some of the
results of [12], in sec. 3 we compute the matrix elements of the setup from
Fig. 1 and show that it coincides with the $K$-theoretic vertex function. In
sec. 4 we use the $R$-matrices in the tensor product of Fock and vector
representation to construct the screened vertex operator which reproduces that
of Shiraishi. We list some of the ideas for the future in sec. 6.

Figure 1: The configuration with spiralling D5q,t/q brane crossing
NS5${}_{q,t^{-1}}$ brane. Every turn of the spiral is shifted by $\mu$ while
the circumference of the circle is $\Lambda$. Pairs of wavy or slanted lines
indicate identification of the branes sticking into them. Notice that the
crossings to the left of the center are over, while those to the right are
under. The Young diagrams $\lambda^{(i)}$ are interlacing as in Eq. (17).
Figure 2: The configuration of $N$ spiralling D3q branes and $N$ horizontal
NS5${}_{q,t^{-1}}$ branes ($N=3$ in the picture). In order not to clutter the
figure not all spectral parameters of the branes are shown.

##  2 Reminder: Hanany-Witten 5-brane crossing operators

Let us remind the main result of [12] (we use the same notation throughout the
paper). It turns out that the $R$-matrix acting in the tensor product
$\mathcal{F}^{(0,1)}_{q,t/q}(w)\otimes\mathcal{F}^{(1,0)}_{q,t^{-1}}(u)$ is
exactly computable and has interesting combinatorial properties. We call the
resulting operator the Hanany-Witten (HW) brane crossing operator. The
$(\lambda,\mu)$ matrix element of the $R$-matrix taken along the vertical Fock
representation in the standard Macdonald polynomial basis is given by:

$\widetilde{\mathcal{R}}^{\lambda}_{\mu}(w,u)=\left(\ldots\otimes\left\langle\mu,\sqrt{\frac{t}{q}}w\right|\right)\mathcal{R}|_{\mathcal{F}^{(0,1)}_{q,t/q}(w)\otimes\mathcal{F}^{(1,0)}_{q,t^{-1}}(u)}\left(|\lambda,w\rangle\otimes\ldots\right)=\\\
=\quad\includegraphics[valign={c}]{figures/d5-ns5-hw-lm-crop}=\\\ =\quad
u^{|\lambda|-|\mu|}f^{\lambda}_{\mu}t^{\frac{\hat{Q}}{2}}\exp\left[-\sum_{n\geq
1}\frac{1-t^{-n}}{n}\left[\frac{1}{1-q^{n}}+\left(\frac{t}{q}\right)^{n}\mathrm{Ch}_{\mu}\left(q^{n},\left(t/q\right)^{n}\right)-\mathrm{Ch}_{\lambda}\left(q^{n},\left(t/q\right)^{n}\right)\right]w^{n}a_{-n}\right]\times\\\
\times\exp\left[\sum_{n\geq
1}\frac{1-t^{n}}{n}\left[\mathrm{Ch}_{\mu}\left(q^{-n},\left(t/q\right)^{-n}\right)-\mathrm{Ch}_{\lambda}\left(q^{-n},\left(t/q\right)^{-n}\right)\right]w^{-n}a_{n}\right],$
(4)

where

$\mathrm{Ch}_{\lambda}(q_{1},q_{2})=\sum_{(i,j)\in\lambda}q_{1}^{j-1}q_{2}^{i-1},$
(5)

the generators $a_{n}$ acting on the horizontal Fock space
$\mathcal{F}^{(1,0)}_{q,t^{-1}}(u)$ satisfy

$[a_{n},a_{m}]=\frac{1-q^{|n|}}{1-t^{|n|}}n\delta_{n+m,0},$ (6)

and the prefactor $f^{\lambda}_{\mu}$ is nonvanishing only when the partitions
$\lambda$ and $\mu$ are _interlacing:_

$f^{\lambda}_{\mu}=0\quad\text{for }\lambda\nsucc\mu$ (7)

which means

$\lambda\succ\mu\qquad\Leftrightarrow\qquad\ldots\geq\lambda_{i}\geq\mu_{i}\geq\lambda_{i+1}\geq\mu_{i+1}\geq\ldots$
(8)

The operator $t^{\hat{Q}/2}$ shifts the spectral parameter $u$ of the
horizontal Fock space by $\sqrt{t}$:

$t^{\hat{Q}/2}|u,\alpha\rangle=|\sqrt{t}u,\alpha\rangle.$ (9)

The interlacing condition (8) endows the $R$-matrix (4) with nice
combinatorial properties. We will use them when we combine several brane
crossing operators together in a chain.

In addition to the formula (4) which can be called the undercrossing (as
evident from the picture) we can derive the formula for _overcrossing,_ i.e.
when the branes pass each other in different order in the $\tau$ coordinate.
This corresponds to evaluating the inverse of the $R$-matrix. We find

$(\widetilde{\mathcal{R}}^{-1})^{\lambda}_{\mu}(w,u)=\left(\ldots\otimes\left\langle\mu,\sqrt{\frac{q}{t}}w\right|\right)\mathcal{R}^{-1}|_{\mathcal{F}^{(0,1)}_{q,t/q}(w)\otimes\mathcal{F}^{(1,0)}_{q,t^{-1}}(u)}\left(|\lambda,w\rangle\otimes\ldots\right)=\\\
=\quad\includegraphics[valign={c}]{figures/d5-ns5-hw-lm-over-crop}=\\\ =\quad
u^{|\lambda|-|\mu|}g^{\lambda}_{\mu}t^{-\frac{\hat{Q}}{2}}\exp\left[-\sum_{n\geq
1}\frac{1-t^{-n}}{n}\left[\mathrm{Ch}_{\mu}\left(q^{n},\left(t/q\right)^{n}\right)-\mathrm{Ch}_{\lambda}\left(q^{n},\left(t/q\right)^{n}\right)\right]w^{n}a_{-n}\right]\times\\\
\times\exp\left[\sum_{n\geq
1}\frac{1-t^{n}}{n}\left(\frac{t}{q}\right)^{n}\left[-\frac{1}{1-q^{-n}}+\mathrm{Ch}_{\mu}\left(q^{-n},\left(t/q\right)^{-n}\right)-\left(\frac{q}{t}\right)^{n}\mathrm{Ch}_{\lambda}\left(q^{-n},\left(t/q\right)^{-n}\right)\right]w^{-n}a_{n}\right],$
(10)

where the prefactor $g^{\lambda}_{\mu}$ now requires $\mu$ to interlace
$\lambda$, not vice versa:

$g^{\lambda}_{\mu}=0\quad\text{for }\mu\nsucc\lambda.$ (11)

Notice that the expression (10) is a generalization of Eq. (67) from [11] to
which it reduces for $\lambda=\mu=\varnothing$.

One can also write down the Hanany-Witten (HW) _move_ [19] relating the over-
and undercrossing operators (4) and (10). The key combinatorial observation is
that if $\lambda\succ\mu$, then $\mu\succ[\lambda\backslash\lambda_{1}]$,
where $[\lambda\backslash\lambda_{1}]$ denotes the Young diagram obtained from
$\lambda$ by removing the first column. We then have

$(\widetilde{\mathcal{R}})^{\lambda}_{\mu}(w,u)\sim\Phi^{q}_{q,t^{-1}}(q^{\lambda_{1}}w)(\widetilde{\mathcal{R}}^{-1})^{[\lambda\backslash\lambda_{1}]}_{\mu}\left(\frac{t}{q}w,u\right),$
(12)

where $\Phi^{q}_{q,t^{-1}}(w)$ is the D3q-NS5${}_{q,t^{-1}}$ brane junction
operator [4]:

$\Phi^{q}_{q,t^{-1}}(q^{\lambda_{1}}w)\sim
u^{\lambda_{1}}t^{\hat{Q}}:\exp\left[\sum_{n\neq
0}\frac{1-t^{n}}{n}\frac{q^{-n\lambda_{1}}}{1-q^{-n}}a_{n}w^{-n}\right]:.$
(13)

Graphically one can picture the HW move as follows:

$\includegraphics[valign={c}]{figures/d5-ns5-hw-lm-
crop}\quad=\quad\includegraphics[valign={c}]{figures/hw-creation-crop}$ (14)

The junction between the dashed blue line and the vertical red line is a
trivial operator cutting the Young diagram $\lambda$ into the first column
$\lambda_{1}$ and the rest of the diagram $[\lambda\backslash\lambda_{1}]$.

As a side remark let us notice a curious fact that the Hanany-Witten _rule_
[19] also holds for the crossing and junction operators that we have
introduced. The rule states that between a given pair of D5q,t/q and
NS5${}_{q,t^{-1}}$ branes there can stretch at most one D3q brane. Indeed, one
can evaluate the operator corresponding to the following picture

$\includegraphics[valign={c}]{figures/hw-
creation-3-crop}\quad\sim\quad\frac{\left(q^{\lambda_{2}-\lambda_{1}};q\right)_{\infty}}{\left(tq^{\lambda_{2}-\lambda_{1}};q\right)_{\infty}}$
(15)

and learn that it vanishes since $\lambda_{1}\geq\lambda_{2}$ in a Young
diagram.

##  3 Spiralling 5-branes and the $K$-theoretic vertex

As noted in [12] the interlacing conditions (7), (11) for the Young diagrams
on the legs of the HW crossings (4), (10) remind one of diagonal slices of a
$3d$ Young diagram (plane partitions). Indeed, if $\pi=\\{\pi^{(i)}_{j}\\}$,
$i,j\in\mathbb{N}$ is a plane partition, so that
$\pi^{(i)}_{j}\geq\pi^{(i+1)}_{j}$, $\pi^{(i)}_{j}\geq\pi^{(i)}_{j+1}$, then
the set of Young diagrams $\\{\lambda^{(i)}\\}$ defined by

$\lambda^{(i)}_{j}=\pi^{(j)}_{i+j-1},\quad i\in\mathbb{Z},j\in\mathbb{N}.$
(16)

satisfies the interlacing conditions

$\ldots\prec\lambda^{(-3)}\prec\lambda^{(-2)}\prec\lambda^{(-1)}\prec\lambda^{(0)}\succ\lambda^{(1)}\succ\lambda^{(2)}\succ\lambda^{(3)}\succ\ldots$
(17)

Notice that the infinite tails in the sequence (17) may have nontrivial
asymptotics.

This makes one wonder if the sequence of Young diagrams (17) can be understood
as living on the legs of a chain of HW crossing operators. It is not hard to
guess the right configuration of branes, which turns out to be a spiralling
D5q,t/q brane crossing a horizontal NS5${}_{q,t^{-1}}$ brane, as shown in Fig.
1. The Figure depicts an intertwining of the DIM algebra involving an infinite
chain of $R$-matrices in which the sum over intermediate states on the
vertical Fock representation corresponds to the sum over _plane partitions._
Let us emphasize this is _not_ the sum over plane partitions featuring in the
(refined) topological vertex/triple 5-brane junction, each slice here
originates from its own segment of the D5q,t/q brane and it is essential that
the number of segments (and crossings) is infinite.

The algebraic expression for the intertwiner in Fig. 1 is

$\mathfrak{R}=\left[\prod_{i=-\infty}^{-1}(\Lambda^{id}\mu^{id^{\perp}}\otimes
1)\mathcal{R}^{-1}(\Lambda^{(1-i)d}\mu^{(1-i)d^{\perp}}\otimes
1)\right]\mathcal{R}\times\\\
\times\left.\left[\prod_{i=1}^{\infty}(\Lambda^{id}\mu^{id^{\perp}}\otimes
1)\mathcal{R}(\Lambda^{(1-i)d}\mu^{(1-i)d^{\perp}}\otimes
1)\right]\right|_{\mathcal{F}^{(0,1)}_{q,t/q}\otimes\mathcal{F}^{(1,0)}_{q,t^{-1}}}.$
(18)

In fact $\mathfrak{R}$ is a _Drinfeld twist_ of the standard DIM $R$-matrix
using the cocycle
$F=\left[\prod_{i=1}^{\infty}(\Lambda^{d}\mu^{d^{\perp}}\otimes
1)\mathcal{R}\right]$. Since $\mathfrak{R}$ acts on the tensor product of two
Fock spaces its matrix elements depend on four Young diagrams — the
asymptotics of the sequences of states on the vertical and horizontal branes.

The next logical question is what natural object can be associated with the
sum over plane partitions? A very interesting candidate is the $K$-theoretic
vertex, the equivariant count of sheaves on $\mathbb{C}^{3}$ [13, 14]. The
vertex is given by an explicit formula:

$I(\lambda,\mu,\nu)=\sum_{\pi}Q^{|\pi|^{\prime}}\exp\left[\sum_{n\geq
1}\frac{1}{n}\chi_{\pi}(t_{1}^{n},t_{2}^{n},t_{3}^{n})\right],$ (19)

where the sum goes over plane partitions with fixed asymptotics
$(\lambda,\mu,\nu)$ along three coordinate axes, $|\pi|^{\prime}$ denotes the
regularized total number of boxes in $\pi$,

$\chi_{\pi}(t_{1},t_{2},t_{3})=\mathrm{Ch}_{\pi}(t_{1},t_{2},t_{3})-\frac{\mathrm{Ch}_{\pi}(t_{1}^{-1},t_{2}^{-1},t_{3}^{-1})}{t_{1}t_{2}t_{3}}+\mathrm{Ch}_{\pi}(t_{1},t_{2},t_{3})\mathrm{Ch}_{\pi}(t_{1}^{-1},t_{2}^{-1},t_{3}^{-1})\frac{(1-t_{1})(1-t_{3})(1-t_{3})}{t_{1}t_{2}t_{3}}$
(20)

and

$\mathrm{Ch}_{\pi}(t_{1},t_{2},t_{3})=\sum_{(i,j,k)\in\pi}t_{1}^{j-1}t_{2}^{i-1}t_{3}^{k-1}.$
(21)

We find quite remarkable that the following theorem holds.

######  Theorem 1.

Up to $\Lambda$\- and $\mu$-independent prefactors the $K$-theoretic vertex
with two nontrivial asymptotics coincides with the vacuum matrix element of
$\mathfrak{R}$

$(\langle\varnothing|\otimes\langle\mu|)\mathfrak{R}(|\lambda\rangle\otimes|\varnothing\rangle)\sim
I(\lambda,\mu,\varnothing)$ (22)

provided one identifies

$\displaystyle t_{1}$ $\displaystyle=\mu^{-1}\sqrt{\frac{t}{q}},$ (23)
$\displaystyle t_{2}$ $\displaystyle=\mu\sqrt{\frac{t}{q}},$ (24)
$\displaystyle t_{3}$ $\displaystyle=q,$ (25) $\displaystyle Q$
$\displaystyle=\Lambda.$ (26)

The proof is straightforward term-by-term analysis of the matrix elements of
$\mathfrak{R}$. Several remarks are in order.

  1. 1.

Notice that $t_{1}t_{2}t_{3}=t$, so one can nicely write three independent
parameters $(t_{1},_{2},t_{3})$ in terms of four parameters
$(t_{1},t_{2},t_{3},(t_{1}t_{2}t_{3})^{-1})=\left(\mu^{-1}\sqrt{\frac{t}{q}},\mu\sqrt{\frac{t}{q}},q,t^{-1}\right)$
with product equal to one.

  2. 2.

In the definition of $\mathfrak{R}$ the built-in symmetry of the DIM algebra
under permutations of $(q,t^{-1},t/q)$ is broken. Instead the new symmetry
between $(t_{1},t_{2},t_{3})$ emerges in a completely nontrivial way.

  3. 3.

It is not hard to add the third nontrivial leg to the vertex by considering
instead of $\mathfrak{R}$, i.e. a product of the form
$\cdots\mathcal{R}^{-1}\mathcal{R}^{-1}\mathcal{R}^{-1}\mathcal{R}\mathcal{R}\mathcal{R}\cdots$,
a more general product of $\pm 1$ powers with the same asymptotics. Such a
pattern of $\pm 1$ powers encodes a Maya diagram which is equivalent to a
Young diagram, which is the diagram living on the third leg in the
$K$-theoretic vertex.

  4. 4.

The infinite wrapping of the D5q,t/q brane and the appearance of $\mu$ as an
extra equivariant parameter in the vertex suggest that the extra sums over an
infinite number of Young diagrams could be rewritten as sums over Kaluza-Klein
modes in the $S^{1}_{y}$ direction. It would be interesting to make this point
more explicit in the future.

  5. 5.

Non-vacuum matrix elements of $\mathfrak{R}$ should give $K$-theoretic vertex
with descendant insertions.

##  4 Shiraishi wavefunctions from spiralling D3-branes

In [15, 16] Shiraishi has introduced a new class of special functions
originally called ‘‘non-stationary elliptic Ruijsenaars wavefunctions’’. We
will call them simply Shiraishi functions for brevity. These functions can be
obtained as matrix elements of a certain screened vertex operator involving
affine system of screening currents. In this section we show that the affine
screening operators featuring in the Shiraishi vertex operator naturally arise
in the wrapped background with spiralling D3q branes.

Consider a tensor product of $N$ horizontal Fock spaces
$\mathcal{F}^{(1,0)}_{q,t^{-1}}\left(p^{\frac{i}{N}}x_{i}\right)$. Then
according to the general formalism [4] there are screening currents between
neighbouring pairs of Fock spaces built from intertwiners of DIM algebra
involving vector representations $\mathcal{V}_{q}$ or $\mathcal{V}_{t^{-1}}$
(these are usually called dual sets of screening charges). However, the
essential difference from [4] arises because the space is now compactified, so
there appears an extra screening charge corresponding to the interaction
between the first and the last Fock spaces in the tensor product.

The Shiraishi wavefunction $f^{\widehat{\mathfrak{gl}}_{N}}$ depends on two
sets of $N$ variables $\mathbf{x}=\\{x_{i}\\}$ and $\mathbf{s}=\\{s_{i}\\}$
and parameters $p$, $\kappa$, $q$ and $t$. It can be defined as a vacuum
matrix element of a vertex operator as follows:

$f^{\widehat{\mathfrak{gl}}_{N}}(\mathbf{x},p^{\frac{1}{N}}|\mathbf{s},\kappa^{\frac{1}{N}}|q,t)=\prod_{1\leq
i<j\leq
N}\frac{\left(\kappa^{\frac{j-i}{N}}t\frac{s_{j}}{s_{i}};q,\kappa\right)_{\infty}\left(\kappa^{\frac{j-i}{N}}\frac{q}{t}\frac{s_{j}}{s_{i}};q,\kappa\right)_{\infty}}{\left(\kappa^{\frac{j-i}{N}}\frac{s_{j}}{s_{i}};q,\kappa\right)_{\infty}\left(\kappa^{\frac{j-i}{N}}q\frac{s_{j}}{s_{i}};q,\kappa\right)_{\infty}}\langle\varnothing|\prod_{i=0}^{N-1}\Phi^{i}(s_{i+1}|t^{\omega^{N-i}}\mathbf{x},p)|\varnothing\rangle,$
(27)

where

$\displaystyle(x;q,p)_{\infty}$ $\displaystyle=\prod_{i,j\geq
0}(1-xq^{i}p^{j}),$ (28) $\displaystyle t^{\omega^{m}}\mathbf{x}$
$\displaystyle=(x_{1},x_{2},\ldots,tx_{N-i+1},\ldots,tx_{N})$ (29)
$\displaystyle\Phi^{i}(s|t^{\omega^{N-i}}\mathbf{x},p)$
$\displaystyle=\sum_{\lambda}\Phi_{\lambda}^{i}(s)\left(p^{\frac{1}{N}}\prod_{j\geq
1}\frac{t^{\delta_{j\mod N,1}}x_{(N-i+j)\mod N}}{x_{(N-i+j-1)\mod
N}}\right)^{\lambda_{j}},$ (30) $\displaystyle\Phi^{i}_{\lambda}(s)$
$\displaystyle=\left(\frac{\left(\frac{q}{t};q\right)_{\infty}}{\left(q;q\right)_{\infty}}\right)^{l(\lambda)}\phi_{i-l(\lambda)}(s)\prod_{j=1}^{l(\lambda)}S_{j-i+1}\left(\kappa^{\frac{l(\lambda)}{N}}q^{\lambda_{j}}s\right),$
(31) $\displaystyle\phi_{i}(s)$ $\displaystyle=:\exp\left[\sum_{n\neq
0}\frac{w^{-n}}{n}\beta_{n}^{(i)}\right]:,$ (32) $\displaystyle S_{i}(w)$
$\displaystyle=:\exp\left[-\sum_{n\neq
0}\frac{w^{-n}}{n}\alpha^{(i)}_{n}\right]:,$ (33)

and the bosonic modes $\alpha^{(i)}_{n}$, $\beta^{(i)}_{n}$ satisfy certain
Heisenberg commutation relations based on the affine root system. The exact
expressions for these commutation relations can be found in [15].

The main theorem in this section states that one can reproduce all the
screening currents and vertex operators in (32) and (33) if one considers the
system of spiralling branes depicted in Fig. 2.

######  Theorem 2.

The vacuum matrix element in the r.h.s. of (27) coincides with the vacuum
matrix element of the intertwiner shown in Fig. 2. The map between the
parameters is already incorporated in the Figure.

The proof is tedious but straightforward and involves checking the commutation
relations of the screening currents and establishing the map between the
parameters of the Shiraishi functions and the spectral parameters of the
representations in the DIM intertwiner. In fact, more can be said: not only
does the vacuum matrix elements coincide, but the screened vertex operator
itself is the same as the intertwiner from Fig. 2.

Notice that Theorem 2 provides the identification between the network of DIM
intertwiners and the wavefunction for completely general parameters. One can
then follow the dictionary between the parameters for any possible
degeneration, such as the one considered in [17].

Having new algebraic view on Shiraishi functions gives us hints about their
properties. In the next section we provide as just one example, the sketch of
a proof of the mirror symmetry of the functions
$f^{\widehat{\mathfrak{gl}}_{N}}$.

##  5 Symmetries of Shiarishi wavefunctions from spiralling branes

Functions
$f^{\widehat{\mathfrak{gl}}_{N}}(\mathbf{x},p^{\frac{1}{N}}|\mathbf{s},\kappa^{\frac{1}{N}}|q,t)$
have nontrivial symmetry properties which are not evident from their
definition. In partocular, they enjoy the so-called mirror symmetry (the exact
prefactor is also known [15], but we will not pursue it here):

$f^{\widehat{\mathfrak{gl}}_{N}}(\mathbf{x},p^{\frac{1}{N}}|\mathbf{s},\kappa^{\frac{1}{N}}|q,t)\sim
f^{\widehat{\mathfrak{gl}}_{N}}(\mathbf{s},\kappa^{\frac{1}{N}}|\mathbf{x},p^{\frac{1}{N}}|q,q/t).$
(34)

In the spiralling branes formalism the symmetry (34) becomes the consequence
of the HW move (14). Indeed, after a little manipulation (attaching the free
ends of the D3q branes to D5q,t/q branes, which adds only a prefactor to the
partition function [11]) one learns that Fig. 2 is equivalent to the following
picture:

(35)

Using the HW move (14) we can eliminate D3q branes altogether and encode their
positions in the pattern of over- and undercrossings:

(36)

It might not be evident from the first sight, but after a little redrawing one
can see that the picture (36) is symmetric under the exchange of the vertical
and horizontal axes and simultaneous swap of red and violet colors (i.e.
$t^{-1}$ and $t/q$ parameters). This proves the mirror symmetry of Shiraishi
wavefunctions.

Spectral duality of the Shiraishi wavefunctions can also be proven along the
same lines, the details of this will appear elsewhere.

##  6 Conclusions

We have introduced new types of brane configurations in Type IIB string theory
on the twisted product $\mathbb{R}^{8}\tilde{\times}T^{2}$. In these
configurations a brane wraps one of the cycles of the torus multiple times
while with every wrapping one of the flat coordinates is shifted by a
constant. It turns out that such brane configurations are meaningful also in
the algebraic formalism in which they correspond to certain DIM algebra
intertwiners.

To justify the usefulness of the spiralling branes we considered two examples
in which the corresponding intertwining operators reproduce beautiful objects
($K$-theoretic vertex function and Shiraishi wavefunctions) that are both of
high importance to general mathematical physics.

We hope that this approach will lead to many new results, however as for now
we have only scratched the surface. Nevertheless we have proven mirror
symmetry of Shiraishi wavefunctions which turns out to be natural in our
formalism. With the new machinery it would also be desirable to understand
Hamiltonians corresponding to ‘‘nonstationary elliptic Ruijsenaars’’ system.

Let us comment on possible connection with the natural generalization of the
$K$-theoretic vertex function — the ‘‘magnificent four’’ vertex function [25],
which is a partition function counting $4d$ Young diagrams (solid partitions).
We conjecture based on the combinatorics of the crossing operators that the
setup similar to that of Fig. 1 but with a D7 brane instead of the D5 brane
will in fact reproduce the magnificent four vertex. In the alebraic language
this corresponds to wrapping the MacMahon representation instead of the Fock
one on the spiral. One can also see that a similar crossing but with
D5${}_{q,t^{-1}}$ crossing NS5${}_{q,t^{-1}}$ leads to a partition function
that can be understood as a particular reduction of the magnificent four
vertex in which the $4d$ Young diagrams are confined to a ‘‘hook’’ in one of
the coordinate planes.

Very recently, $4d$ Young diagrams have also been considered as states of BPS
particles arising from the bound states of branes [26]. It would be
interesting to incorporate them into our algebraic description.

An explicit closed form expression for the $K$-theoretic vertex with two
nontrivial legs was obtained in [24]. Our approach does not seem to give a
reason for the existence of such an expression, however this deserves further
investigation.

We also expect that spiralling branes can be used in the new algebraic
approach to $qq$-characters [23] to accommodate gauge theories with adjoint
matter.

## Acknowledgements

This work is partly supported by the joint grant RFBR 21-51-46010 and TÜBITAK
220N106.

## References

  * [1] J. Polchinski, Cambridge University Press, 2007, ISBN 978-0-511-25227-3, 978-0-521-67227-6, 978-0-521-63303-1 doi:10.1017/CBO9780511816079
  * [2] E. Sharpe, [arXiv:hep-th/0307245 [hep-th]].
  * [3] J. A. Harvey and G. W. Moore, Commun. Math. Phys. 197 (1998), 489-519 doi:10.1007/s002200050461 [arXiv:hep-th/9609017 [hep-th]].
  * [4] Y. Zenkevich, JHEP 08 (2021), 149 doi:10.1007/JHEP08(2021)149 [arXiv:1812.11961 [hep-th]].
  * [5] J. Ding, K. Iohara, Lett. Math. Phys. 41 (1997) 181–193, q-alg/9608002
K. Miki, J. Math. Phys. 48 (2007) 123520

  * [6] Y. Zenkevich, JHEP 12 (2021), 034 doi:10.1007/JHEP12(2021)034 [arXiv:1912.13372 [hep-th]].
  * [7] D. Gaiotto and M. Rapčák, JHEP 01 (2019), 160 doi:10.1007/JHEP01(2019)160 [arXiv:1703.00982 [hep-th]].
T. Procházka and M. Rapčák, JHEP 11 (2018), 109 doi:10.1007/JHEP11(2018)109
[arXiv:1711.06888 [hep-th]].
T. Procházka and M. Rapčák, JHEP 05 (2019), 159 doi:10.1007/JHEP05(2019)159
[arXiv:1808.08837 [hep-th]].
M. Rapčák, JHEP 01 (2020), 042 doi:10.1007/JHEP01(2020)042 [arXiv:1910.00031
[hep-th]].

  * [8] D. Galakhov, Nucl. Phys. B 946 (2019), 114693 doi:10.1016/j.nuclphysb.2019.114693 [arXiv:1812.05801 [hep-th]].
D. Galakhov and M. Yamazaki, Commun. Math. Phys. 396 (2022) no.2, 713-785
doi:10.1007/s00220-022-04490-y [arXiv:2008.07006 [hep-th]].
D. Galakhov, W. Li and M. Yamazaki, JHEP 08 (2021), 146
doi:10.1007/JHEP08(2021)146 [arXiv:2106.01230 [hep-th]].

  * [9] H. Awata and H. Kanno, JHEP 05 (2005), 039 doi:10.1088/1126-6708/2005/05/039 [arXiv:hep-th/0502061 [hep-th]].
A. Iqbal, C. Kozcaz and C. Vafa, JHEP 0910 (2009) 069
doi:10.1088/1126-6708/2009/10/069 [hep-th/0701156].

  * [10] H. Awata, B. Feigin and J. Shiraishi, JHEP 1203 (2012) 041 doi:10.1007/JHEP03(2012)041 [arXiv:1112.6074 [hep-th]].
  * [11] Y. Zenkevich, JHEP 12 (2021), 027 doi:10.1007/JHEP12(2021)027 [arXiv:2012.15563 [hep-th]].
  * [12] Y. Zenkevich, [arXiv:2212.14808 [hep-th]].
  * [13] N. Nekrasov and A. Okounkov, doi:10.14231/AG-2016-015 [arXiv:1404.2323 [math.AG]].
  * [14] A. Okounkov, [arXiv:1512.07363 [math.AG]].
  * [15] J. I. Shiraishi, Journal of Integrable Systems, 4(1) (2019): xyz010. [arXiv:1903.07495 [math.QA]]
  * [16] E. Langmann, M. Noumi and J. Shiraishi, SIGMA 16 (2020), 105 doi:10.3842/SIGMA.2020.105 [arXiv:2006.07171 [math-ph]].
  * [17] M. Fukuda, Y. Ohkubo and J. Shiraishi, SIGMA 16 (2020), 116 doi:10.3842/SIGMA.2020.116 [arXiv:2002.00243 [math.QA]].
  * [18] H. Awata, H. Kanno, A. Mironov and A. Morozov, JHEP 04 (2020), 212 doi:10.1007/JHEP04(2020)212 [arXiv:1912.12897 [hep-th]].
H. Awata, H. Kanno, A. Mironov and A. Morozov, JHEP 08 (2020), 150
doi:10.1007/JHEP08(2020)150 [arXiv:2005.10563 [hep-th]].

  * [19] A. Hanany and E. Witten, Nucl. Phys. B 492 (1997), 152-190 doi:10.1016/S0550-3213(97)00157-0 [arXiv:hep-th/9611230 [hep-th]].
  * [20] H. Awata, H. Kanno, A. Mironov, A. Morozov, A. Morozov, Y. Ohkubo and Y. Zenkevich, JHEP 10 (2016), 047 doi:10.1007/JHEP10(2016)047 [arXiv:1608.05351 [hep-th]].
H. Awata, H. Kanno, A. Mironov, A. Morozov, A. Morozov, Y. Ohkubo and Y.
Zenkevich, Nucl. Phys. B 918 (2017), 358-385
doi:10.1016/j.nuclphysb.2017.03.003 [arXiv:1611.07304 [hep-th]].
H. Awata, H. Kanno, A. Mironov, A. Morozov, K. Suetake and Y. Zenkevich, JHEP
04 (2019), 097 doi:10.1007/JHEP04(2019)097 [arXiv:1810.07676 [hep-th]].

  * [21] M. Jimbo, H. Konno, S. Odake and J. Shiraishi, Transform. Groups 4 (1999), 303-327 doi:10.1007/BF01238562 [arXiv:q-alg/9712029 [math.QA]].
  * [22] M. Ghoneim, C. Kozçaz, K. Kurşun and Y. Zenkevich, Nucl. Phys. B 978 (2022), 115740 doi:10.1016/j.nuclphysb.2022.115740 [arXiv:2012.15352 [hep-th]].
  * [23] M. B. Bayındırlı, D. N. Demirtaş, C. Kozçaz and Y. Zenkevich, [arXiv:2310.02587 [hep-th]].
  * [24] Y. Kononov, A. Okounkov and A. Osinenko, Commun. Math. Phys. 382 (2021) no.3, 1579-1599 doi:10.1007/s00220-021-03936-z [arXiv:1905.01523 [math-ph]].
  * [25] N. Nekrasov, Ann. Inst. H. Poincare D Comb. Phys. Interact. 7 (2020) no.4, 505-534 doi:10.4171/aihpd/93
N. Nekrasov and N. Piazzalunga, [arXiv:2306.12995 [hep-th]].

  * [26] D. Galakhov and W. Li, [arXiv:2311.02751 [hep-th]].