点击下方卡片，关注 「AI视界引擎」 公众号
视觉Transformer（ViTs）在计算机视觉领域带来了革命性的变革，但由于它们在资源受限的设备上的部署仍然具有挑战性，原因在于其高计算需求。为了加速预训练的ViTs，已经开发了Token剪裁和Token合并方法，这些方法旨在减少计算中涉及的Token数量。然而，这些方法仍然存在一些局限性，例如剪裁Token导致的图像信息损失和Token匹配过程的低效性。
在本文中，作者提出了一种新颖的基于图的Token传播（GTP）方法，以解决高效视觉Transformer（ViTs）在平衡模型效率和信息保留方面的挑战。受到图摘要算法的启发，GTP详细地传播重要Token的信息到在空间和语义上相关的Token，这些Token更为重要。因此，剩下的少量Token充当整个Token图的摘要，使得方法在降低计算复杂度的同时保留被剪裁Token的重要信息。结合创新性的Token选择策略，GTP可以高效地确定需要传播的图像Token。
作者进行了大量的实验验证了GTP的有效性，证明了其效率和性能的提升。具体来说，GTP通过在仅微调ImageNet-1K上的0.3%的准确性损失，将DeiT-S和DeiT-B的计算复杂度降低了26%，并且在各种Backbone网络上的推理速度更快地显著超过了最先进的Token合并方法。
- 引言
近年来，视觉Transformer（ViT）迅速成为各种计算机视觉任务的领军框架，在图像分类、目标检测和分割等方面展现出显著的性能。尽管ViT在计算机视觉领域取得了令人瞩目的成就，但其高昂的计算成本却限制了其在计算资源受限的设备上的应用。因此，提高ViT的计算效率已经成为ViT研究中的一个日益受到关注的领域。
为了减轻ViT的计算负担，已经探索了许多方法，例如将自注意力与卷积相结合，并设计区域自注意力。与提出新颖有效ViT架构的方法不同，Token剪裁技术被提出，以加速预先建立的ViT模型。特别地，Token剪裁方法首先测量每个Token的重要性，然后丢弃不重要的Token，旨在逐步减少计算中涉及的Token数量。
在提高模型效率的同时，剪裁图像Token必然会导致被移除Token的不可逆信息损失，从而降低性能，尤其是当大量Token被消除时。此外，Token剪裁方法需要进一步微调以防止显著性能下降，这也增加了它们的计算成本。关于Token剪裁方法的一些缺陷：
图1：**Token减少方法之间的比较，以DeiT模型[38]为Backbone网络。作者的GTP在模型效率和性能之间取得了最佳权衡。
Token剪裁，最近的一项研究[1]提出将Token合并作为一种保持信息和避免微调的方法。然而，Token合并每层需要进行Token匹配过程，其计算复杂度与特征维数和Token数量平方成正比，使其比Token剪裁效率更低。
现有方法的局限性突显了研究挑战：如何有效地平衡ViT模型中的模型效率和信息保留。与此同时，如何在不需要微调的情况下提高预训练ViT模型的效率，同时实现最小化的性能下降也是一个未解决的研究问题，尤其是在计算资源受限的环境中。
在这项工作中，作者提出了一种新颖的基于图的Token传播（GTP）方法来解决这些挑战。受到图摘要技术的启发，作者将Token剪裁和信息保留问题重新定义为Token摘要任务，其中剩下的Token包含了被剪裁Token的信息。
- 首先，作者提出了一种创新而有效的Token选择策略，用于衡量每个Token的重要性。该策略基于每个Token的重生难度和广播能力，这些信息可以从已经在自注意力模块中计算好的注意力图中标中。因此，作者的Token选择策略成对Token匹配更有效，而且可以在没有[CLS]Token的情况下进行。
- 其次，受到图神经网络信息传递机制的启发，GTP构建了一个图像Token图，并将被消除Token的信息传播到图中的邻居。
图2：现有Token剪裁（顶部）、Token合并（中间）和作者的Token总结（底部）方法的比较。Token剪裁和Token总结都可以有效地衡量每个Token的重要性并确定哪些Token应该被丢弃，从而在Token合并之上提供计算优势。然而，只有Token合并和Token总结成功保留了被删除Token的信息。
因此，GTP通过Token之间的多向关系来保留Token信息，而现有的Token合并方法则专门关注一对一的匹配和合并。保留的Token最终构成了图像的较小表示，同时保留了大部分信息。图2说明了作者的方法与先前方法的比较。此外，作者观察到，在预训练的ViT中直接丢弃Token通常会在softmax激活后产生一个更平滑的注意力图。为解决此问题，作者的方法将注意力图稀疏化作为一个反平滑机制。
作者的工作贡献如下：
- 提出了一个新颖而有效的Token选择策略
- 设计了一个基于图的Token传播方法，用于概括整个图像，保留被剪裁Token的信息
- 稀疏化注意力图，以强制Token关注重要信息
- 大量的实验证明了GTP的有效性。值得注意的是，以预训练的DeiT-B为Backbone，GTP在微调成本仅为0.3%的损失下，实现了28%的推理速度提升，并超越了最先进的Token剪裁方法在性能与效率之间的权衡，如图1所示。
2 相关工作
2.1 高效视觉Transformer
自视觉Transformer（ViT）的成功以来，许多研究都在探索高效的ViTs。一些方法设计快速的自注意力计算，它们与输入长度或特征维数的线性或近线性扩展有关。此外，一些方法将自注意力层与高效的卷积层相结合。此外，区域自注意力方法计算自注意力在一个受限制的区域，这些方法在计算上具有优势。
为了降低全局Token交互的计算复杂度，已经提出了许多方法。与这些方法不同，作者的方法专注于使用即插即用的组件加速预训练的ViTs，而不是提出新的Backbone架构。
2.2 Token剪裁和合并
利用图像Token之间的固有冗余性，许多研究试图减少ViTs中的Token数量引入了一个预测模块来确定可以无性能损失地删除的Token。 [25]根据Token对[CLS]Token的关注度来删除Token。 [18]对保留重要Token进行评分和采样。然而，这些方法导致了被剪裁Token的信息损失，并需要从预训练模型中进行微调。除了剪裁方法外，[1]提出了一种Token合并方法，通过合并相似Token来保持信息，而无需进一步微调。作者的方法在这些想法的基础上，引入了一种基于图的Token传播技术，解决了现有Token减少策略的局限性。
3 方法
3.1 初步
1 视觉Transformer
标准的ViT将输入图像划分为几个图像块，然后将这些图像块投影为图像Token嵌入。用表示一个图像的嵌入特征图，其中和分别是Token的数量和特征维数。每个ViT块包括一个多头自注意力（MHSA）层和一个前馈网络层。在MHSA层中，先将归一化的特征图线性变换为Query（）、Key（）和Value（）矩阵。然后，ViT通过Query和Key的点积与softmax激活计算每个Token对之间的相似度。
其中，是注意力图，是的特征维数。此外，MHSA层计算多个注意力图以增加多样性。
2 图神经网络
图神经网络通常由堆叠的消息传递层组成，其中图中的所有节点通过聚合邻居的信息来更新其表示。这种机制也可以看作是每个节点向相邻节点传播其信息。图卷积网络使用卷积操作作为对图结构数据的节点聚合方法。给定一个由节点集和边集组成的图及其邻接矩阵,GCN通过卷积操作更新节点特征图。
其中，是投影权重，表示非线性（即，ReLU），是对称归一化的邻接矩阵，是度矩阵。
3.2 高效的Token传播
1 Token选择
为了确定哪些Token可以传播和丢弃而不会显著牺牲，一个快速有效的Token选择策略至关重要。在作者的方法中，作者从两个方面评估一个Token的重要性。
2 再生难度
作者假设一个Token在自注意力过程中主要由其他Token聚合，那么这个Token的重要性就比其他Token低。这些不太重要的Token可以被丢弃，因为它们更容易由其他Token再生，并且它们的信息在Token总结结果中的重要性较小。具体来说，图像Token的再生难度得分是通过所有其他Token对的注意力之和的负和计算的。
其中，是一个对易位不变的聚合器，用于将多个头中的值融合。更大的表示一个更重要的Token 。因为作者只需要知道不同图像Token对应的s的顺序，而不是它们自身的值，所以公式中的常数项可以省略，从而。因此，对于特征图中的所有图像Token可以直接从其注意力图的主对角线上获得，即。
3 广播能力
尽管再生难度，图像Token如果对自注意力计算中的其他Token有显著贡献，也是不可缺少的。作者通过将这个Token 对所有其他Token的注意力分数相加来量化Token的广播能力，并将其表示为：
广播能力分数反映了Token在向ViT中的其他Token广播信息的重要性。具体来说，用来表示特征图中所有图像Token的广播能力，其中。
4 Token选择
考虑到再生难度分数和广播能力分数，作者保留具有最大值的个Token，并传播剩余的个Token。传播的Token用表示，而保留的Token用表示，其中和分别表示总Token数和传播Token数。此外，作者从Token选择过程中排除[CLS]Token，并默认为保留。特别是，作者默认选择作为。
5 分析
作者的Token选择策略具有三个关键优势：
- 首先，与[21, 34]不同，作者的策略不引入额外的参数
- 其次，与[25]不同，作者的方法可以在没有[CLS]Token的情况下运行，可以将作者的方法扩展到不使用[CLS]Token的ViTs
- 此外，作者的策略在计算上是高效的，因为它不需要计算Token之间的成对相似性，比[1]在实践中更快
Figure 5: 不同Token选择策略的比较。 作者应用不同的Token选择策略与GTP，并报告了传播Token数量为不同值时的top-1精度。 作者在图5中比较了不同的Token选择策略，包括再生难度和广播能力混合策略(MixedAttn)、仅再生难度(DiagAttn)、仅广播能力(BroadAttn)、[CLS]Token注意力(CLSAttn)、Token之间的余弦相似度(CosSim)和随机选择(Random)。
6 稀疏图构建
GTP将图像Token视为图中的节点，并基于Token之间的空间和语义关系构建一个稀疏图。值得注意的是，Token图仅在Token嵌入层构建一次，并在整个网络中保持静态，从而消除了在每一层重复构建的需要。
7 空间图
由于每个图像Token对应于原始图像上的一个区域，作者可以简单地针对Token的原位置在原始图像上生成一个空间图。空间图的邻接矩阵定义如下：
这样，GTP就可以在图表示中捕获图像Token的空间信息。空间图的邻接矩阵对于所有图像都是固定的。
8 语义图
虽然空间图反映了Token之间的空间连接，捕获它们的语义连接也是必要的。作者利用余弦相似度来衡量在初始特征图中Token和之间的语义相似度。
9 余弦相似度
余弦相似度衡量了初始特征图中Token 和之间的语义相似度。
然后，语义图的邻接矩阵定义如下：
其中，表示节点到其他节点的第大余弦相似值（）。作为阈值，确保每个Token最多只有个邻接点。
图3：基于图的Token传播（GTP）可视化。GTP在Token嵌入层之后仅构建一次图像Token图。在每个Transformer块中，GTP利用MHSA层计算的注意力图来估计每个图像Token的重要性分数。然后，它将较不重要的Token传播到重要Token，传播Token之间的边仅来自传播Token到保留Token。因此，剩余Token形成了整个图像的浓缩图表示。
与空间图不同，语义图为Token传播提供图像特定的关系。
10 混合图
接下来，作者生成一个同时表示Token之间的空间和语义关系的混合图，通过将空间图和语义图集成。混合图的邻接矩阵是和的并集。
请注意，3个图中都不包含自环。在GTP中，图结构仅用于将从被消除Token到剩余Token的信息传播出去。因此，被选择的Token无需从自己处收集信息。遵循公式2，作者对图进行对称归一化：
其中，是定义为的对角度矩阵。值得注意的是，Token图仅在Transformer块之前构建一次。
11 实现优化
作者详细介绍了稀疏图传播的实现优化以及确定第大值的快速算法，并将其放在附录中。在随后的实验中，除非另有说明，作者设置。作者还在附录中提供了关于选择的研究。
12 Token总结
受到图神经网络（GNNs）中的信息传递机制的启发，作者提出了Token总结过程，其中图像Token向空间和语义上相关的Token传播其特征。在每个层中，GTP通过广播传播的Token到保留的Token。
其中，是一个超参数，控制传播Token特征的大小。项是从归一化邻接矩阵中提取的，其中行和列索引分别对应保留和传播的Token。是当前层的图像Token的总结，并参与随后的计算。GTP在每一层上立即实现Token传播过程，在Token传播过程之后，作者只保留归一化邻接矩阵以保留的Token。
13 注意力稀疏化
比例注意力
在减少Token数量后，标准的softmax输出变得平滑，这可能会对性能产生负面影响。为了应对这个问题，作者将比例注意力引入到GTP中。比例注意力计算如下：
其中，表示每个Token的大小。此外，作者用和分别表示保留Token和传播Token的大小，其中保留Token的大小根据它所总结的Token数量动态更新。
注意力图稀疏化
除了比例注意力，作者还通过过滤注意力图中的冗余值来改进注意力图。特别地，作者保留注意力图中的最大值，并将剩余元素赋值为零，其中是Token数量，表示注意力图的稀疏度。注意力图稀疏化有助于将Token注意力集中在最重要的信号上，从而减轻注意力图的平滑性并提高模型性能。
4 实验
4.1 实现设置
在本节的所有实验中，作者都在ImageNet-1K数据集上进行图像分类任务，该数据集包含大约128万训练图像和5000个验证图像。作者将验证集上的top-1精度作为主要性能指标。
对于fine-tuned模型，作者使用与DeiT中实现相同的图像增强和训练配方，并仅fine-tune 30个epoch。基本和最小学习率分别设置为和。作者在相同的NVIDIA A6000 GPU上测量GTP和其他所有比较模型的推理速度，除非另有说明，否则固定批量大小为128。作者确保所有模型的PyTorch和CUDA版本相同。
4.2 主要结果
作者首先在预训练的DeiT-S，DeiT-B，LV-ViT-S和LV-ViT-B上应用作者的GTP，不进行额外的fine-tuning，并在表1中呈现了不同传播Token数量下的性能。这四个模型是用于Token剪裁方法的流行的ViTBackbone。表1表明了GTP在不需要fine-tuning的情况下加速ViT的能力。
Table 1: GTP主要结果在ImageNet-1K上_没有fine-tuning_. 在这个表中，作者报告了在不同的超参数设置下，各种传播Token数量下的最佳top-1精度。表示全尺寸backbone模型。请注意，LV-ViT-S和LV-ViT-M [19]最多只能减少每层12和9个Token。
特别地，当每层传播8个Token（即）时，GTP实现了25%的实时吞吐量速度提升（1581.3图像/秒 vs 1268.3图像/秒），计算复杂度降低了26%（3.4 GMACs vs 4.6 GMACs），与全尺寸DeiT-S模型相比，精度下降了0.3%（79.5% vs 79.8%）。即使是更复杂的模型DeiT-B，GTP仍然实现了计算复杂度的26%降低（13.1 GMACs vs 17.6 GMACs）和推理速度的约28%提升（521.8图像/秒 vs 408.8图像/秒），精度下降了0.3%（81.5% vs 81.8%）。作者还将在图4中可视化一些Token总结的示例。
Figure 4: Token总结结果的视觉化。 作者在DeiT-B [38]上应用GTP，并将传播Token数量设置为8。与现有主要关注消除较不重要背景Token的Token剪裁模型不同，GTP确保了某些背景Token的保留，从而提供了原始图像的摘要表示。
4.3 与其他最先进的方法进行比较
Table 2: 与最先进方法进行比较，以DeiT-S为Backbone。 “w/ F”和“w/o F”分别表示带有和不带30个epoch微调的性能。作者将性能按计算复杂性进行分类。例如，_Approx. 3.5GMACs_表示约3.5 GMACs的计算复杂性，相当于DynamicViT，EViT和Tri-Level的保留比率为0.8，Evo-ViT的选择比率为0.7，ATS块（第7至11层）的ATS以及作者GTP的每层减少8个Token。作者利用每个类别中最慢的推理速度（即）作为基准（即）进行速度比较。为确保公平性，作者使用这些模型的官方发布代码重新产生了微调结果。图1显示了可视化比较。粗体字体表示更好。
在表2和表3中，作者呈现了GTP与Token剪裁和Token合并方法（包括DynamicViT，EViT，ATS，Evo-ViT，Tri-Level和ToMe）的比较，包括它们的top-1精度，计算复杂度（以GMACs为单位测量），和推理速度（以每秒图像数量测量）。
作者比较了这些基准，因为它们已经发布了官方源代码，这样作者就可以在有和无fine-tuning的情况下复制这些模型的结果，对于各种计算复杂性。表中的更多实现细节可以在表注释中找到。
表2显示了在DeiT-S上的有fine-tuning和无fine-tuning结果。在相似的推理速度下，GTP可以匹配Token剪裁方法（带有fine-tuning）的性能，并在消除更多Token时超越它们。例如，在相同的计算复杂度（2.6GMACs）下，GTP在top-1精度上超过了EViT的0.2%（79.1% vs 78.9%），这反映了GTP保留信息的能力。
值得注意的是，当大量Token被消除时，Token剪裁方法在无fine-tuning的情况下会遭受严重的精度下降。表3展示了在DeiT-B上的无fine-tuning结果，其中GTP在相似的推理速度下超过了所有比较模型。Token的直接消除导致Token剪裁方法的性能显著下降。
例如，当将DeiT-B的计算复杂度降低到8.8GMACs时，EViT只能获得75.1%的top-1精度，这比其在DeiT-S（76.8%）上的表现（仅2.6GMACs复杂度）要差。相反，GTP达到78.3%的准确率，比EViT高3.2%的top-1准确率。唯一的例外是ATS，它在非常慢的推理速度下保持了性能。这表明Token剪裁方法在保持高效和保留剪裁Token的信息方面存在困难，在无fine-tuning的情况下无效。相反，GTP在无fine-tuning的情况下实现了模型性能和效率的最佳折衷，如图1所示。
为了探究GTP的有效性和泛化性，作者在DeiT-B上进行了消融研究，并报告了不同Token选择策略下的top-1精度（见表2）。作者还进行了Token稀疏化实验，以验证GTP的效率。在表3中，作者比较了不同模型在无fine-tuning下的性能。此外，作者还进行了Token合并实验，以探究GTP对信息保留的影响。
1 Token选择策略
在图5中，作者比较了不同的Token选择策略，包括同时考虑再生难度和广播能力（_MixedAttn_）、仅考虑再生难度（_DiagAttn_）、仅考虑广播能力（_BroadAttn_）、[CLS]Token注意力（_CLSAttn_）[25]、Token之间余弦相似度（_CosSim_）[1]和随机选择（_Random_）。
图5表明，作者的Token选择策略在消除不同数量Token时始终优于其他方法。此外，简单地采用再生难度分数（即_DiagAttn_）可以达到与传统[CLS]注意力接近或更高的性能。考虑到许多新的ViT架构不包含[CLS]Token，作者的方法为它们上的Token剪裁方法提供了一种潜在的解决方案。
2 图类型
作者研究了Token总结过程中的Token图类型，并报告了它们的最佳top-1精度，见表4。Token图类型_None_表示仅选择和删除Token而不进行传播，这与按层Token剪裁类似。对于语义图，作者默认将语义相关Token数量（）设置为8，从而创建一个与空间图等大小的图。
首先，作者注意到仅依赖语义图通常可以获得良好的性能，而使用混合图在大多数场景下。这表明Token之间的语义关系比空间关系更重要。其次，作者观察到图传播的有效性体现在被消除Token数量的增加上。例如，在DeiT-B上，当或时，图传播只能提高top-1精度0.1%，但当时，这个精度差异增加到0.4%。
3 注意力稀疏化
作者在GTP方法中使用的比例注意力进行了消融实验，详细内容见表5。对于DeiT-S，作者观察到比例注意力始终可以提高性能。例如，当时，比例注意力将DeiT-S的最佳top-1精度提高了0.5%。然而，对于仅有的微小改进，在DeiT-B上比例注意力效果较差。然后，作者研究了注意力稀疏度，并呈现了不同注意力稀疏度下的top-1精度。
与比例注意力类似，作者发现注意力稀疏化对较大模型影响较小。例如，当每层移除14个Token时，适当的注意力稀疏度可以使DeiT-S的top-1精度提高0.7%，这比在DeiT-B上的提高0.2%要高得多。作者认为这也是因为较大模型比较小模型更具有鲁棒性，并且已经集中于图像的最重要部分。换句话说，DeiT-B的注意力图已经相当稀疏。
4 反平滑
图6说明了每个Token减少模型中每个层图像Token之间的平均余弦相似度的趋势。较高的平均余弦相似度表示存在严重的过平滑问题，其中所有剩余Token倾向于相似。过平滑会导致GCN和ViT性能下降。作者的GTP可以缓解过平滑问题，并产生较低的图像Token间相似度，这是作者出色性能的一个关键因素。
作者在更多的Token数量下测试了ViT的性能，并报告了结果。作者提供了GTP和ToMe的计算复杂性理论比较。在此部分，作者以ViT-B-Patch8为Backbone进行实证比较。ViT-B-Patch8包含765个Token，远多于ViT-B或DeiT-B的197个Token。表6中的实验结果表明，在BackboneViT中具有更多Token时，作者的GTP实现了更好的性能，推理速度快约10%。
5 GTP在ViTs中不包含[CLS]Token的性能如何？
正如第3.2.1节中所介绍的，GTP不需要[CLS]Token来选择Token。在表7中，作者展示了GTP在ViT-Medium-GAP上的结果，该模型使用全局平均池化代替了[CLS]Token。值得注意的是，[18, 22, 42, 25]不能使用这个Backbone网络。
4.4 实现优化
首先，作者注意到空间图和语义图都是稀疏图，具有图稀疏度和，其中是图像Token的总数。对于ViT和DeiT模型，通常为196，这意味着两个邻接矩阵中少于5%的值是非平凡的。因此，混合图也是稀疏图，其稀疏度不超过（平均小于7%）。
因此，作者可以将图存储在稀疏张量中，并使用稀疏矩阵乘法加速第3.2.2节和第3.2.3节中的图传播。此外，对于稀疏矩阵乘法不支持的批处理输入，作者可以使用散射减少操作避免密集矩阵乘法。其次，语义图的阈值可以通过在非排序的数组中找到第大值确定，其复杂度为，而不是排序整个数组，其复杂度为。
4.5 实验设置
作者在表8和表9中提供了比较方法的超参数设置。这些超参数用于控制Backbone ViT的计算复杂性降低，以确保公平的比较。
图传播超参数
在图总结过程中，作者使用来控制从传播Token到保留Token传播的信息量。
Figure 7: ImageNet-1K上的GTP的Top-1精度随不同变化。 作者评估了在未进行fine-tuning的情况下，GTP在DeiT-S和DeiT-B[38]上的性能，相对于不同的。为了进行公平的比较，作者采用相同的图类型进行传播，并将DeiT-S和DeiT-B的注意力稀疏度分别设置为0.6和0.5。在这个实验中，作者发现不同设置下的结果是一致的。
在本节中，作者研究GTP相对于不同的性能，并在图7中可视化结果。一般来说，当在[0,1]范围内增加时，相应的精度首先上升然后下降，在DeiT-S和DeiT-B之间达到0.2-0.4和0.1-0.3的峰值。
作者从两个方面解释这个现象。首先，当接近0时，传播的信息变得琐碎，导致传播Token的信息无法保存。当时，这个过程仅仅剪枝。其次，随着的增加，传播的信息逐渐主导剩余Token的原信息，导致过平滑问题，并随后阻碍性能。
图邻居数量
Figure 8: DeiT-S和DeiT-B上GTP的Top-1精度与语义邻居数量的关系。 作者评估了在未进行fine-tuning的情况下，GTP在DeiT-S和DeiT-B上的性能，相对于不同的语义相关邻居数量。
作者研究了语义邻居数量对模型性能的影响，并在图8中绘制了准确率。为了进行公平的比较，作者在静态注意力稀疏度和为0.5和0.2的DeiT-S和DeiT-B上应用GTP。图8（a）和（c）分别显示了仅使用语义图进行Token传播时，不同下获得的结果。可以观察到，当传播Token数较小时（例如，或），增加语义邻居首先会略微提高准确率，然后收敛。
然而，当变得较大（例如，）时，增加语义邻居可能导致性能下降。这可以归因于聚合冗余信息，其中一个保留Token包含了过多的传播Token，可能与其语义不密切相关。图8（b）和（d）显示，将语义图与空间图结合可以稳定准确率趋势，表明在Token总结中空间关系的重要性。
计算复杂度比较
正如在引言部分所述，ToMe在成对Token匹配过程中遇到了计算瓶颈，其计算复杂度与特征维度和Token数量平方成正比。与ToMe相比，GTP展示了更快的推理速度。
作为一个即插即用组件，GTP在每个ViT块中将Token总结模块插入到MHSA层和FFN层之间，其行为类似于ToMe。因此，当被消除Token的数量相同，GTP和ToMeBackbone模型的计算复杂性应该相同。因此，作者只考虑这两个模型在本文中引入的额外计算成本（例如，Token匹配、Token选择和Token传播）。在进行理论分析之前，作者将这些成本的表示列在如下：
网 络 中 的 总
数 量
第层的剩余数量,其中
每 个 层 中 的 消 除
数 量
特征维数 总层数 头数
对于ToMe，Token匹配处理首先将Token分为两组，然后计算每对来自两组的Token之间的余弦相似度。在第层，这个过程的计算复杂度为。此外，ToMe在每一层合并个Token，其总计算复杂度在每一层为。因此，ToMe引入的总额外计算复杂度可以计算为：
GTP的计算复杂度如下：
- 构建语义图的计算复杂度为；
- 在第层选择最多个Token的计算复杂度为；
- Token传播的计算复杂度为。
因此，GTP的总计算复杂度为。
因此，GTP的总额外计算复杂度可以计算为：
已知且对于DeiT-S，作者可以得到MMACs，这比MMACs小。在DeiT-B上，且，作者观察到MMACs比MMACs小得多。
Figure 9: ToMe [1]和作者的GTP之间的额外计算复杂性比较。 作者绘制了（a）Token特征维数和（b）Token总数对应的计算复杂性（以MMACs为单位）。
图9说明了与总Token数和特征维度相关的额外计算复杂性变化。显然，作者的GTP引入的额外计算复杂性比ToMe小得多，这表明了在特征维度可能超过1024的大型ViTs上的GTP效率，以及对于Token数可能超过1024的密集预测任务上的ViTs效率。
5 结论
在这项工作中，作者将加速计算受限环境下的ViTs的挑战视为Token总结任务，将减少Token数量。作者提出了一种基于图的Token传播（GTP）方法，不需要fine-tuning。GTP构建了图像Token的稀疏图表示，并基于再生难度和广播能力有策略地选择传播较不重要的Token。然后，GTP将不重要Token的信息传播到其他剩余Token，从而构成了浓缩的Token表示。大量实验证明了GTP的有效性和效率。作者希望作者的工作可以激发未来对ViTs的Token减少研究。
6 参考
[1].GTP-ViT: Efficient Vision Transformers via Graph-based Token Propagation.
点击上方卡片，关注 「AI视界引擎」 公众号