Accelerating Transformers with Spectrum-Preserving Token Merging
Authors: Hoai-Chau Tran
Duy Minh Ho Nguyen
Manh-Duy Nguyen
TrungTin Nguyen
Ngan Hoang Le
Pengtao Xie
Daniel Sonntag
James Zou
Binh T. Nguyen
Mathias Niepert
Venue: NeurIPS 2024 poster (2024)
Keywords: token merging
vision transformer
model compression
Primary area: deep_learning_architectures
TL;DR: a new method for token merging in transformer architecture

Abstract: Increasing the throughput of the Transformer architecture, a foundational component used in numerous state-of-the-art models for vision and language tasks (e.g., GPT, LLaVa), is an important problem in machine learning. One recent and effective strategy is to merge token representations within Transformer models, aiming to reduce computational and memory requirements while maintaining accuracy. Prior work has proposed algorithms based on Bipartite Soft Matching (BSM), which divides tokens into distinct sets and merges the top $k$ similar tokens. However, these methods have significant drawbacks, such as sensitivity to token-splitting strategies and damage to informative tokens in later layers. This paper presents a novel paradigm called PiToMe, which prioritizes the preservation of informative tokens using an additional metric termed the \textit{energy score}. This score identifies large clusters of similar tokens as high-energy, indicating potential candidates for merging, while smaller (unique and isolated) clusters are considered as low-energy and preserved. Experimental findings demonstrate that PiToMe saved from 40-60\% FLOPs of the base models while exhibiting superior off-the-shelf performance on image classification (0.5\% average performance drop of ViT-MAEH compared to 2.6\% as baselines), image-text retrieval (0.3\% average performance drop of Clip on Flick30k compared to 4.5\% as others), and analogously in visual questions answering with LLaVa-7B. Furthermore, PiToMe is theoretically shown to preserve intrinsic spectral properties to the original token space under mild conditions.

Accelerating Transformers with Spectrum-Preserving Token Merging
Hoai-Chau 1,2 Duy M. H. Nguyen 1,3,4 Duy M. Nguyen', TrungTin Nguyen Ngan Le², Pengtao X9e Daniel Sonntag ,100 James Zou'! Binh T. Nguyen Mathias Niepert 3,4
'German Research Center for Artificial Intelligence (DFKI). University of Science VNUHCM *Max Planck Research School for Intelligent Systems (IMPRS-IS), *University of Stuttgart, Dublin City University, University of Queensland, 'University of Arkansas, MMBZAAI, UC San Diego, 1Oldenburg University, Stanford University.
Abstract
Increasing the throughput the Transformer architecture, a foundational com- ponent used in numerous state-of-the-art models for vision and language tasks (c.g., GPT, LLa Va), is an important problem in machine learning. One recent and effective strategy is to merge token representations within Transformer models, aiming to reduce computational and memory requirements while maintaining ac- curacy. Prior works have proposed algorithms based on Bipartite Soft Matching (BSM), which divides tokens into distinct sets and merges the top k similar tokens. However, these methods have significant drawbacks, such sensitivity to token- splitting strategies and damage to informative tokens in later layers. This paper presents novel paradigm called PITOME, which prioritizes the preservation of informative tokens using an additional metric termed the energy score. This score identifies large clusters of similar tokens as high-energy. indicating potential candi- dates for merging, while smaller (unique and isolated) clusters are considered as low-energy and preserved. Experimental findings demonstrate that PITоME saved from 40-60% FLOPs of the base models while exhibiting superior off-the-sheil per- formance on image classification (0.5% average performance drop of ViT-MAEH compared to 2.6% as baselines), image-text retrieval (0.3% average performance drop of CLIP on Flickr30k compared to 4.5% as others), and analogously in visual questions answering with LLaVa-7BB Furthermore, РгтоМF is theoretically shown to preserve intrinsic spectral propertics to the original token space under mild conditions. Our implementation is available this link
1 Introduction
Vision Transformers (ViTs) [ have been integral to recent advancements in computer vision, leading state-of-the-arr the deep learning architectures for representing images and videos (255) However, these transformer-based architectures incur substantial memory costs and have a quadratic time complexity in the number of tokens due to the self-attention layers. This challenge becomes particularly severe as model sizes increase, as observed in Large Language Models (LLLMs) 6).
To address such limitations, several efforts focus designing more efficient attention mechanism by making it linearly scale with input tokens 7 8 integrating vision or language domain-specifte modules [9 [0], pruning the head numbers in ViT [2]. Others propose dynamically pruning less important tokens w.r.t. pre-defined metrics using learnable masks [33 [4]. However, a primary downside of these novel methodologies lies in the necessity to retrain the model from scratch, therefore hindering the leveraging of well-trained models such as LLMs. Morcover, most pruning- based techniques may not accelerate the training process, which arises from the dynamic removal
Cirstt author, 'Corresponding Authors.
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

VIT-B 384
PiToMe (ours)
ToMe
DifTRate
Figure 1: A comparison of token merging methods. Patches of the same color are merged. Green arrows highlight incorrect merges, avoided by PITOME. Position of tokens with high attention scores (cyan borders, zoom for clarity) in PITOME are maintained proportionality akin to ViT-base 384.
of tokens in each sample, resulting in mismatch of dimensions and consequently preventing the batching of samples with consistent dimensions.
Recent research has introduced a novel token merging technique. Instead of pruning, this method combines tokens with high semantic similarity, removing background tokens and merging less informative foreground ones. Its versatility extends to training and non-training scenarios, drastically reducing compute and memory usage. A notable example is ToMe [T]]. which introduced the Bipartite Soft Matching (BSM) algorithm, prominent for its simplicity and effectiveness in merging highly similar tokens. Since ToMe, several works, including ToFu [16], Pumer [17. LTPM [88, and DiffRate [19], have built upon BSM with various adaptations in vision and language domains. In BSM, tokens representing image patches are separated into sets A and B, and their pairwise cosine similarity is computed. The top k similar pairs of tokens between the sets A and B are merged. However, the performance of this algorithm is sensitive to the token-splitting strategy. For instance, ToMe's approach, which first splits tokens based on index parity, can lead to incorrect merging since tokens in A can subsequently only be merged with those in B (Figure [T.. Morcover, while BSM excels in initial layers with many redundant tokens, deeper layers risk merging informative tokens due to latent object correlations. Though current enhancements [19] mitigated this by considering token attention scores in BSM (20), their adaptability different ViT architectures, each with potentially distinct attention score distributions 21,, remains a challenge.
In this work, we propose PITOME (Protect Informative Tokens before Merging), a method designed to safeguard crucial iooommtiion-barinn tokens prior to the merging step. Our method prioritizes preserving informative tokens by utilizing an additional metric termed the energy score inspired by connections to graph energy in spectral graph theory 22 23 (Theorem [D. Specifically, our energy score assesses large clusters of similar tokens possessing high energy (like background and repeated textures), thereby marking them as suitable candidates for merging, while smaller, distinct regions (Foreground) are deemed low-energy and thus treated as protected informative tokens. The proposed energy term operates on the graph built for input tokens, taking into account their relationships and aggregating information from nearby neighbors when their similarities exceed certain thresholds. This approach facilitates a deeper contextual comprehension compared to previous that rely solely on attention scores feature embedding per token. Subsequently,
works [15 [9] we only select the highest-scoring tokens and pass them on for merging in the next steps, ensuring the preservation of important tokens, particularly in the latter stages when only few remaining ones. During the merging process, we continue leveraging sorted energy vectors from earlier stages by distributing tokens with similar energy into two sets, A and B, resulting in candidates in A having a high probability of finding compatible matches in B. Matched tokens are then merged using a weighted average feature embedding to create a new token representation.
The empirical results demonstrate that despite the increased computational cost associated with energy score calculations, PITOME exhibits comparable speed to other BSM-based approaches since the matching is performed on a smaller, high-energy token set. At the same time, it consistently shows superior accuracy across various experimental scenarios. Additionally, we present theoretical insights into PrToME, showing that, under moderate assumptions nature of feature embeddings generated by ViT for node pairs within and across distinct objects our algorithm efficiently preserves the spectral properties of the initial input tokens, maintaining the eigenvalues derived from normalized Laplacian matrices of the original tokens 26). To summarize, our contributions encompass:
such as the discriminative
A new token merging procedure for accelerating VIT architectures is designed to protect crucial yet small-rea small-region tokens while identifying redundant ones for merging based on contextual token correlations captured by our energy score functions.

---

Our PITOME runs as fast as other BSM- based approaches while achieving SOTA per- formance on diverse tasks, ranging from image-text retrieval (Sec. 4.1 visual question answering with LLMs (Sec. 4.2 image classification (Sec. 4.3). and text classification (Sec. 4.4p. In several cases, PPToMe: is shown to reduce up to 60% FL.OPs of base models while only dropping performance around 0.3 0.5% (CLIP model on Flick30k).
We also present theoretical findings indicating that, given reasonable assumptions, PrToME can effectively approximate the spectral distance between the initial token spaces and the merged token set. This sheds light on why PrToME tends to outperform baselines in practical applications and contributes a better understanding the potential limitations inherent in BSM-based methods, such as those in [15 16 17 27
2 Related Work
Efficient A Attention Mechanisms. Various efforts have sought to enhance the efficiency of trans- formers in both NLP and Vision domains. Some concentrate on accelerating attention computation
28 29 g through approximation techniques involving hashing 330, low-rank (31, or sparse approx-
imations [2]. Others explore strategies such as head or feature pruning [1 33 or the integration
34 [Q]. However, many of them necessitate joint training with the backbone model from scratch. For instance, DynamicViT (35] runs approximately 150 hours of fine-tuning on an NVIDIA A A00 GPU to prune the DeiT-S model [36]. In contrast, we focus on accelerating existing ViT models by token merging, which applies training and non-training
of domain-specific modules 22 5
scenarios.
Dynamic Token Pruning. Several studies have explored token pruning in transformer models across NLP 37/39 and vision domains 40 27 However, like efficient transformers, these methods typically require training. Additionally, most pruning techniques are dynamic, meaning the number of tokens varies across different inputs, which improves accuracy but complicates batching for practical deployment. To address this, numerous pruning methods employ masks during the training phase rather than directly eliminating tokens; however, it yields to cancel out the speed advantages associated with pruning-
Token Merging, Leading techniques such as ToMe 15 and its improvements 17 43
build upon lightweight Bipartite Soft Matching (BSM). These methods exhibit speeds comparable to pruning while achieving superior performance. They have demonstrated the ability to double the throughput of otate-of-the-art Vision Transformers (VīT) on both images and videos with minimal accuracy degradation in various scenarios. However, BSM-based approaches are sensitive to the selection of sets in the matching process, potentially resulting in the loss of informative tokens due to heuristic merging procedures. To address these issues, methods like DiffRate [19] and Crossget 44 leverage attention scores in ViT or cross-modal guidance to identify important tokens during the matching process, though they remain sensitive to the distribution of the token space, especially with imbalanced clusters. Another direction involves adapting more intricate algorithms, such k-means [45) spectral clustering [46). graph pooling [47), or graph coarsening [24 48). to merge similar tokens. While these strategies offer some guarantees and well-controlled outputs, their iteration schemes are highly complex and may not align with the goal of reducing model complexity in VIT layers. Our PrToME, the other hand, enables the advantages of both approaches. It maintains efficiency comparable to BSM, remains robust to token partitioning strategies, and offers reasonable trade-off between speed and accuracy. Moreover, PITOME is theoretically proved to approximate the spectral spectrum of the original token space under reasonable assumptions, resembling the behavior of other spectral clustering methods.
3 Methodology
3.1 Token Merging Formulation
We apply token merging to each transformer block of the ViT architecture (Figure a). Given the input token of the (-th block X e Nxh where N and h are the token length and token hidden embeddings, forward step in one Transformer block can be formulated as follows:
X = x' + Attention(X We, X'W K, X'Wv), x X + MLP(X')
(I)
where Attention and MLP the self-attention and multiple layer perceptron components. We then apply merge operations on X and compute the output of the reduced MLP block
x X +MP((X ) where X Fmer (X x k'WK.T)
(2)
3

---

Petateiioain -124-1
New angellack
sagh Wil.!!
Meggellerabe vmage Na)
Deland priceed sode
Mop mergosle and Argentty)
nnih ASM
x
Mas
C potale
MEP C
K" ghan
Sotmas
Figure 2: a) PrTOME can be inserted inside transformer block; b) Energy scores are computed to identify mergeable and protective tokens; c) Our algorithm gradually merges tokens in each block.
is the merging operation that receives X' as input for compressing, X X'W (key matrices) as the token features of X following prior work [15 43 18 19], and r is the fraction of remaining tokens. The output X E B serves input for the MLP layer to produce xi+1 Rrr We present the PrToME F (.) function in the next section.
Here F (.)e(.)
(.)
3.2 Energy-based Merging
We propose to use a new term called energy score to evaluate the redundancy of each token, which is then used to protect informative or isolated tokens (low energy scores) while considering tokens that are in the large cluster as high energy scores and characterizing them as merging candidates. Figure b illustrates the main steps in PrToME.
Token Graph Construction: Given set of N token inputs in X build a weighted graph E, W) with V set of N = [V] nodes, & a set of M = |g| edges defined by connecting one token the remaining ones G. W V be weighted adjacency matrix. We opt for using the key vectors K W E R x as node features of V. i..., 2ù E V has h feature dimensions. The weight W jl assigned an edge Cij E & connects o; and U computed by cosine distance:
U. U2
W - cos Uz), where cos(u;, 0z)
Vu, E V, V, V.
(3)
For simplicity, W and W[: denote the i-th row and column, resp.; [N] stands for (1.....N)
Token Energy Scores: In this step, the energy score, denoted as E (E))te[N) is computed for each node (Figure aaa Step 2). The term is inspired by the concept graph energy in spectral graph theory
22 23 defined as the sum of the absolute eigenvalues of the adjacency matrix W. We also leverage such structures of W to find correlations among tokens and to estimate token redundancy. Instead of using independent token values such attention scores [19], energy leads to better performance (Figure Appendix) and provides theoretical connections to the spectral properties of the original token graphs (Theorem D.
Let i be the index of the current node and Mii) represent the set neighbor nodes. The energy score F; = F,, W(.. :)) of node o; is calculated using the following equation:
E1,,, W [i.
W
1 N
Σ
[ I' (moss v;)), Fm aa(exp(z m) 1) otherwise
if 2 m
(4)
jEN(()
Rather than accumulating all co, vy) values, the function (.)()) in Eq 44. mimics the exponential linear unit activation function [4)]. focusing on similar tokens even if they are far apart, while ignoring dissimilar ones. Here, m a dynamic margin value varying at each layer the ViT model. Nodes within this margin, i.e., (x > m) with high cosine similarity cos(r,, Uz) are considered true neighbors, potentially representing tokens belonging the same object. Nodes outside this margin have cos(e,, 0;) replaced by constant a, providing lower bound for minimal edge weights. The

---

term exp(æ m) 1 < 0 smooths the function fzz for neighboring nodes near the margin m. In experiments, we set a 1.0 and m 0.9 0.9 1,/1, where the current layer index and I is the total number of encoder layers, indicating an increasing margin as tokens move to deeper layers. The ablation studies for the a and m values are presented Section [..
Intuitively, 4 reflects the number of tokens potentially representing the same object. Tokens belonging to large objects (e.g., background) will have high energy scores, indicating potential candidates for merging, while smaller ones (e.g., foreground) will have low energy scores and are considered to be protected. This guides us sort the energy vectors E in descending order and choose only the top 2k nodes with the highest scores as mergeable candidates and the remaining ones as protective tokens, i.e, s = argsort E), merge < s|: 2k), protect + s :], N
Ordered Energy-based Bipartite Soft Matching: Having identified mergeable tokens in the merge set, we continue exploit the sorted order in E to form two sets A and B in BSM, each containing k nodes. Specifically, tokens with odd and even indices in merge are selected for A and B, resp. given the fact that those in the same object should have similar energy scores, resulting in likely distributing in consecutive positions in argsort (E). In other words, our choosing has high probability that one token in A always finds its best match in the same object in B. This sets us apart with random partitions based on spatial indices in images like [5 16].
Tracking Token Sizes All nodes in set A then merged with their nearest neighbors in set through the fast BSM algorithm. Following prior works [[5] [6]. we also add propor- tional attention to balance the effect of the merged token the output of the softmax function:
A Softmax x''QQ (X' //h + log m where m is a row vector containing the size of each token, i.e., the number of data patches the token represents. The pseudo-code for our method is provided in Algorithm|] (Appendix) with complexity analysis.
3.3 Connection to Graph Coarsening with Spectral Preservation
In this section, we employ tools from spectral graph theory show a spectral distance preservation of PITOME. We note that similar properties can be obtained by using more complicated clustering algorithms such as K-mean
[ or spectral clustering 46 47 24]; however, these methods are typically loop- based algorithms, which are computationally expensive and not suitable for batch-type data. Our PITOME, in contrast, is as fast as BSM methods but theoretically preserves spectral properties of input token graphs
We begin by introducing Definitions and 2 of graph coarsening and lifting, resp., to justify the spectral distance constructed in equation (5), measuring the similarity between the original and coarse graphs. For more thorough coverage of the mathematics of graph coarsening and graph lifting, refer the reader to (50H53). In short, we treat the result of token merging as a graph coarsening process (Figure g Appendix). We then create the lifted graph as a reconstruction from this coarsened version to assess the spectral distance to the original token graph.
Definition 1 (Graph Coarsening). Given weighted graph G(V, E, W), we denote P = (Vi heei where V Usejm V,, be a partition of its node into n disjoint sets. The coarsened graph of g w.r.t. P is the weighted graph G... where each partition in P is aggregated into a single node, denoted (ui) by averaging the elements within each partition. The elements of the adjacency matrix are given by Weli. Σv,ev, Sr,,vE,,ee Ev,ey, W (// ([V./)))))). We denote the combinatorial and normalized Laplacians of G by L = D W and L = IN - DD11/WDD-1 1/2,, resp., where D is the diagonal degree matrix with D(i, d; = Σラ= Wii, j.. Similarly, the definition of the coarsened
Laplacian matrices follows directly: L. De We and C. In DD. 1 W W.D. -1/2 Finally, the eigenvalues and eigenvectors of L (resp. Le) are denoted as X and u (resp. d and ue).
Definition 2 (Graph Lifting). We call (V(,,, Et, Wi) the lifted graph of G if the adjacency matrix elements are given by Wili.il = W.l..)l. We denote the node degree of Uts E V1 by di Σj=1 Wiii j]. The combinatorial and normalized Laplacians Gf is then defined as L Dr D and Li = IN 1111 /D, resp., where Dj is the diagonal degree matrix with D 0 du- Then, we denote, resp., the eigenvalues and eigenvectors of Li by X and u,
5

---

Lemma 1 (Eigenvalue Preservation, see e.g., of the lifted graph x contain all the eigenvalues of the coarse graph X and additional eigenvalues 1 with (N - n) multiplicity.
54,551555551 The normalized Laplacian eigenvalues
Through Lemma
we can use the lifted graph Gr as a proxy for the coarse graph Ge. and define:
N
SD(G, = - A = Σ
ax - Ati as a spectral distance.
(5)
i=1
Next, we present our main theoretical result demonstrating how spectral distance characterizes the superiority of our novel PITOME paradigm over the state-of-the-ar approaches as ToMe [I5] [6]. The Theorem I quantifies how similar the original G is to its coarsened counterpart Ge, and is proved in Appendix
Theorem (Spectrum Consistent of Token Merging), Suppose the graphs 96"²) DpiToMu and G are coarsened from the original graph G by iteratively merging pairs of nodes Va, and ub, w.r.t. the
true partition pb" ( hels), the PITOME PrToMt--artition PPItOME (V (vr defined by
PITOME in Algorithm L and the ToMe-pariition 17 16), Plite = (V Iveee
NN...,
1. We assume some standard mild assumptions: (AI) Blcos(Va,, vb,)] 1, Vea, =y()) Ver, E v i E [s]; (A2) there exists a margin m s.t., cos(Ua, v. 2 m > cos(va,, Ve.), Yua, E Vve, E Vig) Vi # j [s]; and (A3) there is order of cardinality in the true partition, without loss of generality, we assume N(() 2 N(()) 2... N(a), where N((0) (oee) 1 Vi E [s]. Then it holds that:
Poe Vub, E v/(i) Toi,Ve,
The spectral distance between the original G g6 and the PrToMR-coarse Geriom graphs converges to 0, i.e., SD(G, SpTToMe) ++0, O,
1.
2. The spectral distance between the original G and the ToMe-coarse g(m) graphs converges a non-negative constant C, with high probability that C > 0.
Intuitively, Theorem 1 states that, given assumptions (i) tokens are closely embedded within classes and distinct between classes (AI, A2), and (ii) the number of tokens per class follows certain orders ( (A3), the spectral distance between PrToME and the original tokens in Eq. will converge to O. In contrast, with ToMe partitions, a non-eliminable constant likely remains.
Experiments
We focus on two settings: Off-the-Shelf Performance, where we evaluate the models' performance immediately after compression without training, and Retrained where we treat the compression algorithms as pooling functions and retrain the models on downstream tasks. The experiments cover four tasks: (i) image & text retrieval, (ii) visual question answering (VQA), (iii) image classification, and (iv) text classification. We use the number of floating-point operations (FLOPS) needed for inference on one sample as the main metric to benchmark memory footprint and speed. Higher FLOPS indicate greater memory requirements and longer training and inference times.
4.1 Image & Text Retrieval
We evaluate PITOME on the image-text retrieval task using three different backbone models CLIP [56]. ALBEF [57] and BLIP (58] on two frequently used Flickr30k (59) and MSCOCO (6) datasets.
Our experiment is benchmarked using recall@k [61]. where a higher recall@k indicates the model's effectiveness in retrieval. In Figure we benchmarked PITOME against other SOTA merging or
pruning-base methods such as ToMe 15 ToFu [16,, DattRate 19) and DCT (62 on off-the-sheif setting when varying amount of merged tokens at each layer. Given the same FLOPS, it is clear that PIToME consistently outperforms previous compression algorithms across all backbones. The performance gap increases as we decrease the percentage r of tokens retained in each layer. The same behavior remains consistent in Table 2] where we set r = 0.925 and retrain pre-trained checkpoints of BLIP and CLIP. For more details about the training method, please refer to Li et al. [58).
In Table we compare PiToME using compression ratios of r E (0.95, 0.975) on BLIP and BLIP-2 against other advanced architectures such ViLT 663. LightningDOT (64, UNITER (65)

---

METER [66], CLIP-L [67] and ALBEF [68] The results show that PITOME consistently surpasses those architectures by a significant margin. Moreover, the performance drop on the base BLIP/BLIP-2 is minimal while achieving substantial reductions in memory footprint and rerank times nearyy halving for BLIP and tripling for BI.I-2. Additionally, the speedup can further improve with increased batch and model sizes.
4.2
Visual Question Answering (VQA) with Large Vision-Language Models
This experiment focuses on assessing the off-the-shelf performance of large vision-language models like LLaVa (2]. We extensively conduct experiments across six VQA datasets: VQA-v2
[69],
GQA 170 (academic questions), VizWiz [71] (visually impaired individuals), ScienceQA 772 (zero-
shot scientific question answering), Tex [73] (text-rich VQA tasks), and MME- PaMe-eeecnetionn [74]
(visual perception with yes/no question). More details the number of samples in each dataset
in the Appendix. All experiments are conducted using LLAVA-1.5 7B and LLAVA- 1.5 13B with the
Imms eval library 75 provided by the LMMs-Lab team.
CLIP-L FlCck30k
ALBEF-3 FlGck33kk
BLI-B Flckr30k
100
250
100
120
140
182
35
42
33
40
45
50
CLIP- MS-COCO
ALBEF-B M5-COCO
BLIP- MS-COCO
algi torelhe
pRams
100
120
1.60
100
180
35
65
50
55
60
45
55
65
gfupp
gfass
pTop
Figure 3: Off-the-shell Image-Text Retrieval comparison between PITOME v.s. merging/pruning
methods on different backbones on tasks when varying the number of merged tokens. Here, Recall sum =R + Rt@5 + Rt@10 + Ri@1 Ri@5 + Ri@10 10 is close to 600, indicating recall scores at top 1,5, and 10 for retrieving image and text reached close to 100%. PITOME curves, in most cases, above other baselines.
Table 2:
Retrained Image-Texx Retrieval comparison when retrain- ing from scratch on CLIP and BLIP backbones. Rk Rk@1 + Rk@5 RA@10, k E (t, f).
Table 1: Image- Retrieval comparison. PгTоME with- out training are in blue, and with training in gray. PITOME achieves SOTA while saving 36% 56% in FLOPS and speed- ing up by x.4 to x1.6 compared to the base models.
Datasets
Mechods
R1l11 Rrom
(25 Retrieval
Recunked
Rram
FLOPS
VII
FLOPS
Total
22 Ketreval Totel
Time
Time
Models
Alga.
RE
RiT GRLOPS1
Speed
Eval
Speed!
Trsin
VET
83.50
61:40
.550.41
$35.70
55.81
LishingDOT
$3,90
09.00
532.26
UNITER
321.50
940.9
ToMe
241.30
230.52
12.10
s1.39
x1.29
CLIPE
03.90
61:34
156.25
$0.45
25c
CLiP
Tufu
279.70
258-32
250.08
255.24
12. 10:10
10
s1.39
s1.30
x1.26
ALBES
PITOME4LP
94.91
05.75
65.32
56.32
564.55
567.55
575.00
537.51
55.14
38.55
$5.54
47.55
136
16:
586
565
PYTOME
278.94
$2.10
v1.39
96.61
87.18
$69.96
579.35
38.55
47.65
136
866
Buseise
205.70
21.1.00
11:00
11:00
(1.00
SLIP
PITOMs
06.35
57.03
57.84
565.25
560/76
35.14
390.77
15.5
lin21s
10.17%
DCT
ToMe
241 75
375.55
251
K1.52
x1.57
x1.65
x1.61
11:45
Ind4
752.77
370 219-46
11.57
x1.65
x1.59
PYToMs
353.16
61.57
N1.66
Hoadine:
012.31
11.00
11.00
CLINA
Tibte
245.54
235.03
12. 10:10
11.36
x1.79
METER
76.15
$7.05
495.55
248.00
235.35
12. 10
11.39
XS-COCO
PITOMBOLP
AL REF
277
80.44
76.94
75.45
63.01
67.50
64:34
435.00 00
475,
413.55
$13.6
500.44
905.45
55.14
35.85
15.45
55 54
47 65
47.65
51c
50c
43c
Amdl
PYTOME
245.97
250.76
215.45
237.01
12.10
63.10
11.30
s1.39
x1.29
$1.79
PITOME
BLIP
PITOMS
51.32
63.54
64.35
451.4
515005
434.90
35.14
$64.78
390.77
15.54
Smilk
Lads
9m24
BLI
ToMe
DCT
200.44
206.11
261.15
770.19
-31.87
-14.67
31.57
31.97
31.57
31.90
11.00
11.35
-1.85
235.11
x1.57
31.54
PIToME:
7

---

Let L denote the number of layers in the CLIP encoder and N the number of visually encoded tokens. In our experiment, we apply PITOME to the ViT vision encoder of LLAVA, retaining only percent of tokens in each layer. This results in rf N tokens being fed into the L.M,, significantly enhancing inference speed. We used LLaVA-1.5-7B and 1.5 checkpoints to run off-the-shelf
settings. Tables 3 and E along with Figure 4 illustrate that the РгтоМR algorithm consistently achieves superior performance compared to other merging and pruning methods, as well as existing SOTA models such as BLIP-2 176). InstructBLIP [77]. IDEFICS-
(78), with inference time nearly halved. Remarkably, in some datasets like WisWiz and ScienceQA, the compressed model even surpasses the baseline model. We contend that this improvement stems from the merging of less significant tokens in PITOME. potentially enhancing the robustness of the language model (LLM).
4.3 Image Classification on Imagenet-Ik
In this task, we employed five ViT backbones of varying sizes-tiny (ViT-T), small (ViT-S), base (ViT-B), large (ViT-L), and huge (ViT-H)- which are pre-trained using either MAE 79 or DEIT 80 styles. These backbones were utilized to assess both off-the-shelf and retrained performance. All experiments were conducted on the ImageNet- Ik dataset, which is a subset of ImageNet [8] containing labeled images spanning 1000 categories.
sclenteGA mage
Table 3: Off-the-shelf LLaVA-I.5 7B (r=0.9) and LL- 1.5 13B (r=0.925) performance vs. PIToME and other token pruning/merging methods on six VQA datasets: VQA-v2 [69.
1.50
C.60
2675
GQA (70) VisWiz (7T) TextVQA 773, MME 77 ScienceQA
image (ScienceQA)) ) 772.
2005
Model
LLM
|VA GQA
VisWiz? ScienceAA TeaVQA 1 MME
loxiage
BLIP2
Vicuna 13B
41.0
41.0
19.6
61.0
42.5
1293.8
InstrciBLIP
Vicona-70
34.5
InstuctRl
V3
49.5
1212.8
040
IDEIICS99
LLaMA-7B
500
38.4
35.5
25.9
025
IDEFICS S0B
655
60.0
45.2
36.0
30.9
0:10
LLaVA-1.5-7B
76.6
62.0
54.4
70.4
46.0
1514.7
023
piome
ToMe
1412.4
DCT
ToFu
Vicuna 7B
67.8
75.1
56.2
55.7 7
65.8
26.3
1193.9
1405.5
DiffRate
72.0
57.9
55.4
66.4
30.6
1341.0
PITOME
75,4
59.9
$5.9
69.0
43.0
1448.1
LLaVA-1.5-13B
78.3
1522.6
076
ToMe
76.0
59.9
55.9
1470.3
DCT
DifRate
ToFu
Vicuma1338
76.1
73.4
70.8
$7.3
60.1
58.5
56.1
54.6
56.1
70.3
74.0
70.6
23.9
43.0
32.8
1395
1355.8
1471.0
873
Ago
PiTOME
1491.
840
886
066
Table 4: Inference time of LLaVA-1.5-7B and LLaVA-115- 13B models when running on five V100-GPUs and five A100-
843
GPUs.
Model
VQA
GQA
VisWiz L
StienceQA")
TestVQAi
MME
LLava-15-78
09h,05aa
10m:244
(44m 36.
01m:50s
10mm:24
32m:33
ToMe
0Sa:35e
06m:34s
03m:26s
0lm:07s
07m::7s
01m:24
Totu
055:35m
06m:32s
03m:255
Otmates
07m:40is
01m:24s
054
pirne
DCT
(Sh:59es
06mi414
03m 28s
Olmen8s
064
01m:27
DifERate
0Sh:39t
06m:39s
033:26s
Olm:0es
07mm36s
01m:2ss
PiTOME
0Shoi44m
06m:374
03m:26.
0lmo07s
07m:37
01m:23s
220
LLava-1.5-13B
13m:05
07m:36
Olm:54s
15m:04s
02m:50
0465
040
0.00
1.00 2.34
1000 1822
0.25
0.0
ToMe
09h:28m
09m:35
05m:58.
0m:31s
Hm:484
02m:16s
Tol'u
09h:26ca
09m32s
05m:58s
Wm:26s
11m:45
(2m::15
Figure 4: Off-the-shelf per- formance of PITOME on LLaVA-1.5-7B with different compressing ratio r.
DCT
10m:5%a
06m446
05m455
12m:574
42m:34
DiERate
09h:33m
09mm4s
06m:0ss
00:37
Hmm52s
02m:: SS
PiToME
096:522s
09m:39s
06m333
00m:35
12m:088
02m:17
Table 5 and F present our experimental results, comparing PrToME with recent works, includ- ing SOTA efficient transformers such as Swin-B B [82), CSWin-B [82). MVIT-B/L [83. MAE (79]. and other token merging/prunnin methods [84] 85 41]. We observe that PITOME maintains high accuracy with an average performance drop of only 0.5% after reducing up to 44% of FLOPS
(MAE-H), showcasing superior performance with comparable throughput. It is important to note that dynamic pruning- praning-based methods such A-VIT (85). Dynamic ViT (84). and SP-ViT [13 do not accelerate training speed due to using additional masks for padding tokens into a same dimension. On the retraining settings, we note that models compressed by PITOME also surpass merging/pruning methods by a large margin and approach the performance of the original models.
8

---

4.4 Text Classification
While previous studies have focused on benchmarking BSM-based algorithms within the vision or language domain, we also extend experiments to the text domain, where input sequence lengths vary by sample. Specifically, we apply compression algorithms to the first three layers of the BERT model [86] reducing the number of tokens by 20% in each layer. Our experiments utilize the SST-2 dataset [87] with an average sequence length of 23.2 tokens and the IMDb dataset an average sequence length of 292.2 tokens.
[8]] with
As demonstrated in and Figure 11 (Appendix), our findings indicate that PITOME performs better than other BSM-based baselines. Additionally, after retraining, the compressed BERT models achieve competitive records while significantly accelerating training speed compared to previous pruning methods such as PowER BERT (89), Fisher [90], and LTP [91], as well as BERT-based effi- cient models like DRT [92] and ALBERT 193). Notably, we observe only 0.4% performance drop on the IMDb dataset and even surpass the original BERT model by 0.3% on the SST-2 dataset. For detailed empirical results this task, please refer to Appendix D
Table 6: Text Classification: PITOME vs other BERT-style
Table 5: Image Classification: Per-
compressed models and token pruning ones.
formance of PiToME on Imagenet- Ik, both off-the-shelf (OTS acc) and after retraining (Trained acc), across ViT backbones. We benehmark with differ- ent architectures and merging/pruning methods.
Datasct
Type
Model
Eval Flops
Train Speed
compressed models
ALBERT
91.3
x1.1
DistileBERT
91.1
x2.0
x1.7
BERT
x1.0
pruning -mack
Fisher
91.3
x1.6
x1.0
SST-2
LIP
91.3
x2.9
x1.0
PIToMs
91.0
x1.9
x1.4
Type Model
OTS Trainel
Acc.
Acc.
Flops
speed
Train
merging
ToFu
ToMe
91.2
59.8
x1.9
x1.9
x1.4
K1.4
Otherr CSWin-B
SwinsB
n/a
I/a
84.2
84.0
15.4
15.0
DiftRate
x1.4
models
MVTTV-BB
84.4
1022
PITuMs:
91.7
X1.9
MVTVV-4
85.3
42.1
compressed models
ALBERT
80.2
x1.0
x1.2
68.9
7000
0.79
DistledBERT
93.0
x2.0
x1.9
ToFy
89.6
70.5
0.79
X1.0
merge
DCT
67.6
68.7
0.79
pouning
PowER- BEKT
92.5
x2.7
x1.0
DiTRang
69.9
70.7
0.79
-mask
TR-BERT
93.6
x2.3
81.0
PiToMs SETT
71.6
LMU6
PiToMM:
93.2
x1.9
K1.8
72.3
72.3
1.3
ToMe
x1.9
x1.8
ToFu
78.6
2.9
X
x1.8
prune
SR-VI
79.3
79.3
2.9
Dif'Rate
PrToMs:
92.4
93.6
x1.9
x1.9
x1.8
x1.8
79.5
2.9
ToMesuns
72.7
70.4
2.9
DelT models
MAM models
zaegee
ToFi TITa
77.8
79.6
2.9
07.5
78.6
26-9
DiflRane mons
70.8
79.5
2.9
00.5
PiToME:
79.1
79,8
2.9
79.8
modd
Lave
ToMe
ToPyMAEL
N2.9
83.8
85.0
85.1
31.0
31.00
06R1--1-224
021T--5-224
margo
DiTRaa
PITOME MAEL
82.8
84.6
85.3
K5.3
84.4
31.0
31.0
31.0
70a
12.5
MAL-0-1--244
R5.7
65.7
61.6
673
14220-1--244
ToMpaman
85.6
85.4
92.8
0
2014
27d
234
ToFu MARH
86.4
DCT
84.3
85.0
92.8
85.9
85.6
92.8
Figure 5: Off-the-shelf results on Imagenet-1k. Zoom in for better view.
PITOME
86.4
86.7
92.8
Sabil
167.4
4.5 PITOME Ablation Studies
Contributions of energy scores and related factors. To assess the performance of the components used in PITOME, we conduct the following settings: (i) PITOME without protecting important tokens by our energy in Step 2, i.c., using odd and even indices in sorted energy score array as two sets in BSM; (ii) PITOME where the merging process in Step 3 conducted on two randomly sets A, B as instead of leveraging ordered in sorted energy vectors E(.): (iii) PITOME without using proposed energy score in Eq(4) but utilizing other indicators like attention scores from the [CLS] (PITOME w cls attn) token [9 or mean of attention scores; (iv) PITOME using a fixed of l removed token at each layer as ToMe [15] rather than reducing ratio of r as our configuration.
baselines 15 16
We run experiments on image-text retrieval and text classification tasks, reporting the results Table for (i) and (ii), and in Figure 6 for (iii) and (iv). The results demonstrate that all factors contribute to

---

the performance of PITOME, with energy-based operations playing a particularly significant role. Additionally, reducing tokens with a ratio r effectively eliminates redundant tokens in early layers while preserving informative ones in later layers.
Margin m and hyper-parameters. To validate the roles of these parameters in our energy score function in Eq. 4 we conduct ablation studies on image-text retrieval task with (v) adaptive margin m compared with fixed value m E {0.9, 0.45, 0.0, -1.0] when varying the ratio r and (vi) given fixed value of changing the smooth constant value in ax (<xxp(= - m) - 1) with & < m. Results for these settings are summarized Figure 7 and Table respectively. We observe that while models with fixed tend to have the accuracy drop sharply when it is lower than some threshold, the adaptive margins achieve the best results across cases. We hypothesize that the token space becomes sparser in deeper layers, PiToMe's fixed m approach likely assigns the same energy score to all tokens, making it difficult to isolate and protect tokens during merging. Table also shows that a the best choice across margin values.
Further details, including additional ablation study results, visualizations (output merging, open-chat with Va), and extra PITOME experiments, are provided in the Appendix.
Table 7: Impact of different settings in Steps 2 and 3. Table 8: Impact of the constant a on the
image-text retrieval task. Results are in re- call sum; higher is better.
Image- Text Retrieval
Text CLS.
Settings
ratio
Rsum
ratio
PITOME w/o
0.925
568.9
0.6
86.99
ration
0.5
a 0.
protecting tokens
0.95
575.3
0.7
89.97
step
0.975
578.2
0.8
91.67
0,85
519.98
518.66
515.90
0.875
545.90
544.22
542.54
PiToME using
0.925
567.9
0.6
87.17
rundom split
0.95
574.7
0.7
90.34
0.90
562.82
562.42
561.92
in step
0.975
578.4
0.8
91.73
0.925
571.88
571.10
570.62
0.95
577.50
577.43
$77.40
0.925
573.4
0.6
89.20
PITOME
0.95
$77.8
0.7
91.47
0.975
580.24
579.82
579.76
0.975
580.1
0.8
93,26
580
570
570
560
Recall sim
setting
540
none
250
530
pitome w cls atth
540
ottn
pitome use k
m=0.45
-.-- tome use k
45
50
55
60
65
47.5
50.0
525
55.0
ghlops
Figure 7: Ablation studies on adaptive mar- gin m.
gllsse
Figure 6: Ablation studies of PITOME.
Conclusion
This paper introduces PIToME, a novel algorithm that employs energy concepts to protect informative tokens during the token merging process. Our algorithm matches the efficiency of heuristic merging methods while maintaining a theoretical connection to the spectral properties of the input token space, In experiments on image classification, image-text retrieval, and VQA with LL.VA-1.5 7B/13B, PrToME consistently outperforms recent token merging and pruning methods, given the equivalent runtime and memory usage.
Limitations and Future Works Although our focus has been on tasks using ViT encoders for a variety of applications, we believe it is important to extend PITOME generative tasks such as image generation (e.g., stable diffusion) or segmentation. This extension, however, necessitates the development of unmerge mechanism in the decoder, which remains open question. Additionally, our energy score relies on a fully connected graph of imput tokens, which can increase complexity as the input size grows. Constructing sparse graphs, therefore, might be beneficial for scaling in more challenging settings. Finally, designing a differentiable learning mechanism to optimize the reducing rate for token merging could enhance robustness and versatility across different downstream tasks.
10

---

Acknowledgment
The authors thank the International Max Planck Research School for Intelligent Systems (IMPRS-IS) for supporting Duy M. H. Nguyen. Duy M. H. Nguyen and Daniel Sonntag are also supported by the XAINES project (BMBF, 01IW20005), No-IDLE project (BMBF, 011W23002), and the Endowed Chair of Applied Artificial Intelligence. Oldenburg University. Hoai-Chau Tran acknowledges the support from the AISIA Extensive Research Assistant Program 2023 (Batch 1) during this work and DFKI for supporting computing resources. TrungTin Nguyen acknowledges support from the Australian Research Council grant DP230100905. Ngan Le acknowledges funding support from the U.S. National Science Foundation (NSF) under Award No. 0IA-1946391 and NSF EFRI BRAID 2223793. Binh T. Nguyen wants to thank the University of Science, Vietnam National University Ho Chi Minh City for their support. Mathias Niepert acknowledges funding by Deutsche Forschhugggemmeinccaatt (DFG, German Research Foundation) under Germany's Excellence Strategy -ECC and support by the Stuttgart Center for Simulation Science (SimTTech).
References
[1] 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, 2020.
[2] Haotian Liu, Chunyuan Li, Qingyang Wu, and Yong Jae Lee. Visual instruction tuning, Advances in neural information processing systems, 36, 2024.
[3] Duy MH Nguyen, Hoang Nguyen, Nghiem Diep, Tan Ngoc Pham, Tri Cao, Binh Nguyen, Paul Swoboda, Nhat Ho, Shadi Albarqouni, Pengtao Xie, et al. Lvm-med: Learning large-scale self-supervised vision models for medical imaging via second-order graph matching. Advances in Neural Information Processing Systems, 36, 2024.
[4] Alexander Kirillov, Eric Mintun, Nikhila Ravi, Hanzi Mao, Chloe Rolland, Laura Gustafson, Tete Xiao, Spencer Whitehead, Alexander C Berg, Wan-Yen Yen Lo, et al. Segment anything. In Proceedings of the IEEE/CVF International Conference on Computer Vision, pages 4015-4026, 4026, 2023.
[5] Ze Liu, Jia Ning, Yue Cao, Yixuan Wei, Zheng Zhang, Stephen Lin, and Han Hu, Video swin transformer. In Proceedings of the IEEE/CVF conference on computer vision and pattern recognition, pages 3202-3211, 2022.
[6] Mostafa Dehghani, Josip Djolonga, Basil Mustafa, Piotr Padlewski, Jonathan Heek, Justin Gilmer, Andreas Peter Steiner, Mathilde Caron, Robert Geirhos, Ibrahim Alabdulmohsin, et al. Scaling vision transformers to 22 billion parameters. In International Conference on Machine Learning, pages 7480-7512. PMLR, 2023.
[7] Angelos Katharopoulos, Apoorv Vyas, Nikolaos Pappas, and François Fleuret. Transformers are mns: Fast autoregressive transformers with lincar attention. In International conference on machine learning, pages 5156-5165, PMLR, 2020.
[8] Daniel Bolya, Cheng- Yang Fu, Xiaoliang Dai, Peizhao Zhang, and Judy Hoffman. Hydra attention: Efficient attention with many heads. European Conference on Computer Vision, pages 49. Springer, 2022.
[9] Ze Liu, Yutong Lin, Yue Cao, Han Hu, Yixuan Wei, Zheng Zhang, Stephen Lin, and Baining Guo. Swin transfommrr: Hierarchical vision transformer using shifted windows. In Proceedings of the IEEF/CVF international conference on computer vision, pages 10012-10022, 2021.
[10] Duy MH Nguyen, Hoang Nguyen, Truong TN Mai, Tri Cao, Binh T Nguyen, Nhat Ho, Paul Swoboda, Shadi Albarqouni, Pengtao Xie, and Daniel Sonntag. Joint self-supervised image- volume representation learning with intra-inter contrastive clustering. Proceedings of the AAAI Conference on Artificial Intelligence, volume 37, pages 14426-14435. 2023.
11

---

[11] Lingchen Meng. Hengduo Li, Bor-Chun Chen, Shiyi Lan, Zuxuan Wu, Yu-Gang Jiang, and Ser- Nam Lim. Adavit: Adaptive vision transformers for efficient image recognition. In Proceedings of the IEEE/CVF Conference on Computer Vision and Patlern Recognition, pages 12309-12318 2022.
[12] Paul Michel, Omer Levy, and Graham Neubig. Are sixteen heads really better than one? Advances in neural information processing systems, 32, 2019.
[13] Zhenglun Kong, Peiyan Dong, Xiaolong Ma, Xin Meng. Wei Niu, Mengshu Sun, Xuan Shen, Geng Yuan, Bin Ren, Hao Tang, et al. Spvit: Enabling faster vision transformers via latency- aware soft token pruning. In European conference on computer vision, pages 620-640. Springer, 2022.
[14] Siyuan Wei, Tianzhu Ye, Shen Zhang, Yao Tang, and Jiajun Liang. Joint token pruning and squeezing towards more aggressive compression of vision transformers. In Proceedings of the IEEF/CVF Conference on Computer Vision and Pattern Recognition, pages 2092-2101, 2023.
[15] Daniel Bolya, Cheng-Yang Fu, Xiaoliang Dai, Peizhao Zhang, Christoph Feichtenhofer, and Judy Hoffman. Token merging: Your ViT but faster. In International Conference on Learning Representations, 2023.
[16] Minchul Kim, Shangqian Gao, Yen-Chang Hsu, Yilin Shen, and Hongxia Jin. Token fusion: Bridging the gap between token pruning and token merging. In Proceedings of the IEEE/CVF Winter Conference on Applications of Computer Vision, pages 1383-1392, 2024.
[17] Qingqing Cao, Bhargavi Paranjape, and Hannaneh Hajishirzi. PuMer: Pruning and merging tokens for efficient vision language models. In Anna Rogers, Jordan Boyd-Graber, and Naoaki Okazaki, editors, Proceedings of the 61st Annual Meeting of the Association for Computa- tional Linguistics (Volume 1: Long Papers), pages 12890- 12903, Toronto, Canada, July 2023. Association for Computational Linguistics. doi: 10.186 1/2023.ac acl- aaw.002...-oo...2221 721..
[18] Maxim Bonnaerens and Joni Dambre. Learned thresholds token merging and pruning for vision transformers. Transactions on Machine Learning Research, 2023. ISSN 2835-8855 8856.
[19] Mengzhao Chen, Wenqi Shao, Peng Xu, Mingbao Lin, Kaipeng Zhang, Fei Chao, Rongrong Differentiable compression rate for efficient vision transformers. In 2023 IEEE/CVF International Conference Computer Vision (ICCV), pages doi: 10.1 /ttp://CCC/1100.2222..011
Ji, Yu Qiao, and Ping Luo. Diffrate :
17118-17128, 2023.
[20] Chaoya Jiang, Haiyang Xu, Chenliang Li, Ming Yan, Wei Ye, Shikun Zhang, Bin Bi, and Songfang Huang. Trips: Efficient vision-and aaiion-nddlanne languagg pre-training with text-relevant image patch selection. In Proceedings of the 2022 Conference on Empirical Methods in Natural Language Processing, pages 4096, 2022.
[21] Namuk Park, Wonjae Kim, Byeongho Heo, Taekyung Kim, and Sangdoo Yun. What do self- supervised vision transformers learn? International Conference on Learning Representations, 2023.
[22] R Balakrishnan. The energy of a graph. Linear Algebra and its Applications, 387:287-225. 2004.
[23] Ivan Gutman and Bo Zhou. Laplacian energy of a graph. Linear Algebra and its applications, 414(1):29-37, 2006.
[24] Andreas Loukas and Pierre Vandergheynst. Spectrally approximating large graphs with smaller graphs. In International conference machine learning, pages 3237-3246. PMLR, 2018.
[25] Yu Jin, Andreas Loukas, and Joseph JaJa. Graph coarsening with preserved spectral properties. In International Conference on Artificial Intelligence and Statistics, pages 4452-4462. PMLR, 2020.
(26) Andreas Loukas. Graph reduction with spectral and cut guarantees. Journal of Machine Learning Research, 20(116):1-42, 2019.
12

---

[27] Hongjie Wang. Bhishma Dedhia, and Niraj K Jha. Zero-tprune: Zero token pruning through leveraging of the attention graph in pre-trained transformers. arXiv preprint arXiv:2305.17328, 2023.
[28] Zhuoran Shen, Mingyuan Zhang, Haiyu Zhao, Shuai Yi, and Hongsheng Li. Efficient attention: Attention with linear complexities. In Proceedings of the IEEE/CVF winter conference on applications of computer vision, pages 3531-3533 2021.
[29] Tri Dao, Dan Fu, Stefano Ermon, Atri Rudra, and Christopher Ré. Flashattention: Fast and memory-efficient exact attention with io-awareness, Advances Neural Information Processing Systems, 35:16344-16359, 2022.
[30] Giannis Daras, Nikita Kitaev, Augustus Odena, and Alexandros G Dimakis. Smyrf-efficient attention using asymmetric clustering. Advances in Neural Information Processing Systems, 33: 6476-6489, 2020.
[31] Valerii Likhosherstov, Krzysztof M Choromanski, Jared Quincy Davis, Xingyou Song, and Adrian Weller. Sub-linear memory: How make performers slim. Advances in Neural Information Processing Systems, 34:6707-6719, 2021.
[32] Hongyu Ren, Hanjun Dai, Zihang Dai, Mengjiao Yang, Jure Leskovee, Dale Schuurmans, and Bo Dai. Combiner: Full attention transformer with sparse computation cost. Advances in Neural Information Processing Systems, 34:22470-22482, 2021.
[33] Mohsen Fayyaz, Soroush Abbasi Koohpayegani, Farnoush Rezaei Jafari, Sunando Sengupta, Hamid Reza Vaezi Joze, Eric Sommerlade, Hamed Pirsiavash, and Jürgen Gall. Adaptive token sampling for efficient vision transformers. European Conference on Computer Vision, pages 396-414, Springer, 2022.
[34] Wenhai Wang, Jifeng Dai, Zhe Chen, Zhenhang Huang, Zhiqi Li, Xizhou Zhu, Xiaowei Hu, Tong Lu, Lewei Lu, Hongsheng Li, al. Internimage: Exploring large-scale vision foundation models with deformable convolutions. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 14408-14419, 2023.
[35] Yongming Rao, Wenliang Zhao, Benlin Liu, Jiwen Lu, Jie Zhou, and Cho-Jui Hsieh. Dynamicvit: Efficient vision transformers with dynamic token sparsification. Advances in neural information processing systems, 34: 13937-13949, 2021.
[36] Hugo Touvron, Matthieu Cord, Matthijs Douze, Francisco Massa, Alexandre Sablayrolles, and Hervé Jégou. Training efitaeeffiiient image transformers & distillation through attention. In International conference machine learning, pages 10347-10357. PMLR, 2021.
[37] Saurabh Goyal, Anamitra Roy Choudhury, Saurabh Raje, Venkatesan Chakaravarthy, Yogish Sabharwal, and Ashish Verma. Power-bert: Accelerating bert inference via progressive word- vector elimination. In International Conference on Machine Learning, pages 6699. PMLR, 2020.
[38] Qihuang Zhong, Liang Ding, Juhua Liu, Xuebo Liu, Min Zhang, Bo Du, and Dacheng Tao. Revisiting token dropping strategy in efficient bert pretraining, arXiv preprint ar 212::23055.1573, 2023.
[39] Jungmin Yun, Mihyeon Kim, and Youngbin Kim. Focus on the core: Efficient attention via pruned token compression for document classification. In The 2023 Conference on Empirical Methods in Natural Language Processing, 2023.
[40] Hongxu Yin, Arash Vahdat, Jose Alvarez, Arun Mallya, Jan Kautz, and Pavlo Molchanov. A-vit: Adaptive tokens for efficient vision transformer. In Proceedings of the IEEF/CVF Conference on Computer Vision and Pattern Recognition, pages 10809-10818, 2022.
[41] Yuxuan Zhou, Wangmeng Xiang, Chao Li, Biao Wang, Xihan Wei, Lei Zhang, Margret Keuper, and Xiansheng Hua. Sp-vit: Learning 2d spatial priors for vision transformers. In The 33rd British Machine Vision Conference, 2022.
13

---

[42] Zhuoran Song, Yihong Xu, Zhezhi He, Li Jiang, Naifeng Jing, and Xiaoyao Liang, Cp- vit: Cascade vision transformer pruning via progressive sparsity prediction. arXiv preprint arXiv:2203.045700 2022.
[43] Daniel Bolya and Judy Hoffman. Token merging for fast stable diffusion. 2023 IEEE/CVF Conference on Computer Vision and Pattern Recognition Workshops (CVPRW), pages 4599- 4603, 2023.
[44] Dachuan Shi, Chaofan Tao, Anyi Rao, Zhendong Yang, Chun Yuan, and Jiaqi Wang. Crossget: Cross- gooss- ensemble of tokens for accelerating vision-aanguage transformers. International Conference on Machine Learning, 2024.
[45] Dmitrii Marin, Jen-Hao Rick Chang, Anurag Ranjan, Anish Prabhu, Mohammad Rastegari, and Oncel Tuzel. Token pooling in vision transformers for image classification. In Proceedings of the IEEE/CVF Winter Conference on Applications of Computer Vision, pages 12-21, 2023,
[46] Filippo Maria Bianchi, Daniele Grattarola, and Cesare Alippi. Spectral clustering with graph neural networks for graph pooling. In International conference on machine learning, pages 974-883, PMLR, 2020.
[47] Junran Wu, Xueyuan Chen, Ke Xu, and Shangzhe Li. Structural entropy guided graph hierar- chical pooling. In International conference on machine learning, pages 24017-24030. PMLR, 2022.
[48] Manoj Kumar, Anurag Sharma, Shashwat Saxena, and Sandeep Kumar. Featured graph coarsening with similarity guarantees. In International Conference on Machine Learning, pages 17953-17975. PMLR, 2023.
[49] Djork-Amé Clevert, Thomas Unterthiner, and Sepp Hochreiter. Fast and Accurate Deep Network Learning by Exponential Linear Units (ELUs). In ICLR 2016, 2016.
[50] Yu Jin, Andreas Loukas, and Joseph JaJa. Graph Coarsening with Preserved Spectral Properties. In Silvia Chiappa and Roberto Calandra, editors, Proceedings of the Twenty Third International Conference on Artificial Intelligence and Statistics, volume 108 of Proceedings of Machine Learning Research, pages 4452 4462. PMLR, August 2020.
[51] Andreas Loukas Graph Reduction with Spectral and Cut Guarantees. Journal of Machine Learning Research, 20(116):1-4,,, 2019.
[52] Christopher Brissette, Andy Huang, and George Slota. Spectrum Consistent Coarsening Approximates Edge Weights. SIAM Journal on Matrix Analysis and Applications, 44(3): 1032-1046, 2023, doi: 10.1137/21M1433
[53] Andreas Loukas and Pierre Vandergheynst. Spectrally Approximating Large Graphs with Smaller Graphs. In Jennifer Dy and Andreas Krause, editors, Proceedings of the 35th Inter- national Conference on Machine Learning, volume 80 of Proceedings of Machine Learning Research, pages 3237-3246. PMLR, July 2018.
[54] Hannu Toivonen, Fang Zhou, Aleksi Hartikainen, and Atte Hinkka. Compression of weighted graphs. In Proceedings of the 17th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD 11I pages 965-973, New York, NY, USA, 2011. I. Association for Computing Machinery. ISBN 978- 978-1-45003-0813-7 doi: 10.1145/2020408.200 2..22002000..2222666
[55] Steve Butler. Interlacing for weighted graphs using the normalized Laplacian. The Electronic Journal of Linear Algebra, 16:90-98, 2007.
[56] Alec Radford, Jong Wook Kim, Chris Hallacy, Aditya Ramesh, Gabriel Goh, Sandhini Agar- wal, Girish Sastry, Amanda Askell, Pamela Mishkin, Jack Clark, Gretchen Krueger, and Ilya Sutskever. Learning transferable visual models from natural language supervision. In Marina Meila and Tong Zhang, editors, Proceedings of the 38th International Conference on Machine Learning, volume 139 of Proceedings of Machine Learning Research, pages 8748-8763, PMIR, 18-24 Jul 2021.
14

---

[57] Junnan Li, Ramprasaath R. Selvaraju, Akhilesh Deepak Gotmare, Shafiq Joty, Caiming Xiong, and Steven Hoi. Align before fuse: Vision and language representation learning with momentum distillation. In NeurIPS, 2021.
[58] Junnan Li, Dongxu Li, Caiming Xiong, and Steven Hoi. BLIP: Bootstrapping language-image pre-training for unified vision-language understanding and generation. In Kamalika Chaudhuri, Stefanie Jegelka, Le Song, Csaba Szepesvari, Gang Niu, and Sivan Sabato, editors, Proceedings of the 39th International Conference on Machine Learning, volume 162 of Proceedings of Machine Learning Research, pages 18888-12908 PMLR, 17-23 Jul 2022.
[59] Bryan A. Plummer, Liwei Wang, Chris M. Cervantes, Juan C. Caicedo, Julia Hockenmaier, and Svetlana Lazebnik. Flickr30k entities: Collecting region-tophraan correspondences for richer image-to-sentence models. In Proceedings of the IEEE International Conference on Computer Vision (ICCV), December 2015.
[60] Tsung- Yi Lin, Michael Maire, Serge Belongie, James Hays, Pietro Perona, Deva Ramanan, Piotr Dollár, and C. Lawrence Zitnick. Microsoft coco: Common objects in context. In David Fleet, Tomas Pajdla, Bernt Schiele, and Tinne Tuytelaars, editors, Computer Vision ECCV 2014, pages 740-755, Cham, 2014. Springer International Publishing. ISBN 978-3-319-10602-1.
[61] Min Cao, Shiping Li, Juntao Li, Liqiang Nie, and Min Zhang. Image-text retrieval: A survey on recent research and development. Thirty-First International Joint Conference on Artificial Intelligence (IJCAI)), 2022.
[62] Ziwei He, Meng Yang, Minwei Feng, Jingcheng Yin, Xinbing Wang, Jingwen Leng, and Zhouhan Lin. Fourier transformer Fast long range modeling by removing sequence redundancy with fft operator. In Findings of the Association for Computational Linguistics: ACL 2023. Association for Computational Linguistics, 2023. doi: 10. 10.18653/11/0233 /20.://///.....nnnnnnaa......... acc.ings-
[63] Wonjae Kim, Bokyung Son, and IIdoo Kim. Vilt: usioo-and-languaae transformer without convolution or region supervision. In International conference on machine learning, pages 5583-5594, PMLR, 2021.
[64] Siqi Sun, Yen-Chun Chen, Linjie Li, Shuohang Wang, Yuwei Fang, and Jingjing Liu. Lightning- dot: Pre-training disual-semantic embeddings for real-time image-text retrieval. In Proceedings of the 2021 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, pages 982 997, 2021.
[65] Yen-Chun Chen, Linjie Li, Licheng Yu, Ahmed El Kholy, Faisal Ahmed, Zhe Gan, Yu Cheng, and Jingjing Liu. Uniter: Universal image-text representation learning. In European conference on computer vision, pages 104-120. Springer, 2020.
[66] Zi-Yi Yi Dou, Yichong Xu, Zhe Gan, Jianfeng Wang, Shuohang Wang. Lijuan Wang, Chenguang Zhu, Pengchuan Zhang, Lu Yuan, Nanyun Peng, et al. An empirical study of training end-to-end vision-and-languall transformers. In Proceedings of the IEEF/CVF Conference on Computer Vision and Puttern Recognition, pages 18166618176, 2022.
[67] Alec Radford, Jong Wook Kim, Chris Hallacy, Aditya Ramesh, Gabriel Goh, Sandhini Agarwal, Girish Sastry, Amanda Askell, Pamela Mishkin, Jack Clark, et al. Learning transferable visual models from natural language supervision. In International conference on machine learning. pages 8748-8888888 -7688877..7778 PMLR, 2021.
[68] Junnan Li, Ramprasaath Selvaraju, Akhilesh Gotmare, Shafiq Joty, Caiming Xiong, and Steven Chu Hong Hoi. Align before fuse: Vision and language representation learning with momentum distillation. Advances in neural information processing systems, 34:9694-9705, 2021.
[69] Yash Goyal, Tejas Khot, Douglas Summers- Summers-Stay, Dhruv Batra, and Devi Parikh. Making the V in VQA matter: Elevating the role of image understanding in Visual Question Answering. In Conference on Computer Vision and Pattern Recognition (CVPR), 2017.
[70] D. A. Hudson and C. D. Manning. Gqa: A new dataset for real-world visual reasoning and compositional question answering. In 2019 IEEF/CVF Conference on Computer Vision and Puttern Recognition (CVPR), pages 6693-6702, Los Alamitos, CA, USA, jun 2019. IEFE Computer Society. doi: 10.1109/CVPR.200990066
15

---

[71] Danna Gurari, Qing Li, Abigale J. Stangl, Anhong Guo, Chi Lin, Kristen Grauman, Jiebo Luo, and Jeffrey P. Bigham. Vizwiz grand challenge: Answering visual questions from blind people. In 2018 IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 3608-3611 2018. doi: 10.1109/CVPR..C 2018...0.00.008800
[72] Pan Lu, Swaroop Mishra, Tony Xia, Liang Qiu, Kai-Wei Chang, Song- Chug-Chun Zhu, Oyvind Tafjord, Peter Clark, and Ashwin Kalyan. Learn to explain: Multimodal reasoning via thought chains for science question answering. In The 36th Conference on Neural Information Process- ing Systems (NeurlPS), 2022.
[73] Amanpreet Singh, Vivek Natarajan, Meet Shah, Yu Jiang, Xinlei Chen, Dhruv Batra, Devi Parikh, and Marcus Rohrbach. Towards vqa models that can read. In 2019 IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), pages 8309 0319-8338,11 2019. doi: 10.1109/
CVPR.2019.00851.
[74] Chaoyou Fu, Peixian Chen, Yunhang Shen, Yulei Qin, Mengdan Zhang, Xu Lin, Jinrui Yang, Xiawu Zheng, Ke Li, Xing Sun, Yunsheng Wu, and Rongrong Ji. Mme: A comprehensive evaluation benchmark for multimodal large language models. arXiv preprint vrxiv:2306.139/4 2023.
[75] Bo Li, Peiyuan Zhang, Kaichen Zhang, Fanyi Pu, Xinrun Du, Yuhao Dong, Haotian Liu, Yuanhan Zhang. Ge Zhang, Chunyuan Li, and Ziwei Liu. Lmms-eval: Accelerating the development of large multimoal models, March 2024.
[76] Junnan Li, Dongxu Li, Silvio Savarese, and Steven Hoi. BLIP-2: Bootstrapping language- image pre-training with frozen image encoders and large language models. In Andreas Krause, Emma Brunskill, Kyunghyun Cho, Barbara Engelhardt, Sivan Sabato, and Jonathan Scarlett, editors, Proceedings of the 40th International Conference Machine Learning, volume 202 of Proceedings of Machine Learning Research, pages 19730-19742. PMLR, 23-29 Jul 2023.
[77] Wenliang Dai, Junnan Li, Dongxu Li, Anthony Meng Huat Tiong, Junqi Zhao, Weisheng Wang, Boyang Li, Pascale N Fung, and Steven Hoi. Instructblip: Towards general-purpose vision-language models with instruction tuning. Advances in Neural Information Processing Systems, 36, 2024.
[78] IDEFICS. Introducing idefics: An open reproduction of state-of-the-an visual language model. https://nuggingface co/blog/ idefics 2023. Accessed: 2023-05-21.
[79] Kaiming He, Xinlei Chen, Saining Xie, Yanghao Li, Piotr Dollár, and Ross Girshick. Masked autoencoders are scalable vision learners. arXiv:2111.06377 2021.
[80] Hugo Touvron, Matthieu Cord, Matthijs Douze, Francisco Massa, Alexandre Sablayrolles, and Herve Jegou. Training data-efficient image transformers & distillation through attention. In International Conference on Machine Learning, volume 139, pages 10347-10357, July 2021.
[81] Olga Russakovsky, Jia Deng, Hao Su, Jonathan Krause, Sanjeev Satheesh, Sean Ma, Zhiheng Huang, Andrej Karpathy. Aditya Khosla, Michael Bernstein, Alexander C. Berg. and Li Fei-Fei. ImageNet Large Scale Visual Recognition Challenge. International Journal of Computer Vision (IJCV), 15(3):211-25 2015. doi: 10. 10.1007/s11223 1263-015-8---
[82] Xiaoyi Dong, Jianmin Bao, Dongdong Chen, Weiming Zhang, Nenghai Yu, Lu Yuan, Dong Chen, and Baining Guo. Cswin transformer: A general vision transformer backbone with cross-shaped windows, 2021.
[83] Yanghao Li, Chao- Wu, Haoqi Fan, Karttikeya Mangalam, Bo Xiong, Jitendra Malik, and Christoph Feichtenhofer. Mvitv2: Improved multiscale vision transformers for classification and detection. In CVPR, 2022.
[84] Yongming Rao, Wenliang Zhao, Benlin Liu, Jíwen Lu, Jie Zhou, and Cho-Jui Hsieh. Dynam- ievit: Efficient vision transformers with dynamic token sparsification. In Advances Neural Information Processing Systems (NeurIPS), 2021.
16

---

[85] Hongxu Yin, Arash Vahdat, Jose Alvarez, Arun Mallya, Jan Kautz, and Pavlo Molchanov. A-ViT: Adaptive tokens for efficient vision transformer. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, 2022.
[86] Jacob Devlin, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova. Bert: Pre-training of deep bidirectional transformers for language understanding. Proceedings of naacL-HLT, 2019.
[87] Richard Socher, Alex Perelygin, Jean Wu, Jason Chuang, Christopher D Manning, Andrew Ng, and Christopher Potts. Recursive deep models for semantic compositionality over sentiment treebank. In Proceedings of the 2013 conference on empirical methods in natural language processing, pages 1631-1642, 2013.
[88] Andrew Maas, Raymond E Daly, Peter T Pham, Dan Huang, Andrew Y Ng, and Christopher Potts, Learning word vectors for sentiment analysis. In Proceedings of the 49th annual meeting of the association for computational linguistics: Human language technologies, pages 142-150,
2011.
[89] Saurabh Goyal, Anamitra Roy Choudhury, Saurabh Raje, Venkatesan Chakaravarthy, Yogish Sabharwal, and Ashish Verma. Power-bert: Accelerating bert inference via progressive word- vector elimination. In International Conference on Machine Learning, pages 3690-3699.
PMLR, 2020.
[90] Woosuk Kwon, Sehoon Kim, Michael W Mahoney, Joseph Hassoun, Kurt Keutzer, and Amir Gholami. A fast post-training pruning framework for transformers. Advances in Neural Information Processing Systems, 35:24101-24116 2022.
[91] Sehoon Kim. Sheng Shen, David Thorsley, Amir Gholami, Woosuk Kwon, Joseph Hassoun, and Kurt Keutzer. Learned token pruning for transformers. In Proceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pages 784-794, 2022.
[92] Victor Sanh, Lysandre Debut, Julien Chaumond, and Thomas Wolf. Distilbert, a distilled version of bert: smaller, faster, cheaper and lighter. arXiv preprint arXiv: 108, 2019.
[93] Zhenzhong Lan, Mingda Chen, Sebastian Goodman, Kevin Gimpel, Piyush Sharma, and Radu Soricut. Albert: A lite bert for sulf-supervised learning of language representations, arXiv preprint arXiv:1909. 1942 2019.
[94] Henry Wolkowicz and George P. H. Styan. Bounds for eigenvalues using traces. Linear Algebra and its Applications, 29:471-506, 1980. ISSN 0024-3795. doi: https://doi.org/10.0000 3724-3795580))0258888 X.
[95] Hermann Weyl. Das asymptotische Verteilungsgesetz der Eigenwerte linearer partieller Differen- tialgleichungen (mit einer Anwendung auf die Theorie der Hohlraunstrahlung), Mathematische Annalen, 71 (44):41-4799 December 1912. ISSN 1432-1807. doi: 00.1007//F01456800
17

---

Supplement to " "Accelerating Transformers with Spectrum-Preserving Token Merging"
Contents
A Datasets Deseriptions
18
B PiToME Algorithm
19
B.1 Pseudo-Code Implementation
19
B.2 PIToME Complexity Analysis
19
B.3 Model complexity analysis
20
Performance of ToMe with Different Token Merging Schedules
20
D
Additional Experiments on Text Classification Task.
21
Proof of Theorem
22
E,
Sketch of Proof
22
F,2
Proof of Proposition
23
E.3
Proof of Proposition
24
E,4
Proof of Proposition
24
E.5
Proofs of Technical Results
26
Token Merging Outputs Visualization
29
ChenChat with Compressed 1.. Model
29
Candidate Node
Merged Node
Input graph:
Coarsened graph: Ge
Figure Token merging outputs can be seen as coarsened graph from an input graph.
A Datasets Descriptions
We present in Table 9 datasets used in our experiment. is important to note that PITOME was run off-the-shelf on large datasets in VQA tasks such VQA-v2 with 447.8k sample GQQ with 12.5 questions, validating generalization and robustness of our merging mechanism.
18

---

Table 9: Brief statistic of all datasets used in this paper.
Task
Name
Modality
No. Train
Test
Text retrieval
Flickr80k
59
Vision, Text
29k images, each with captions
Ik images, each with 5 captions images,
approx 118k imuges,
captions
captions
COCO
60
VQA-v2 69
Vision. Text
approx 3.3. questions
approx 447, 8k, questions
GQA 70
Vision. Text
approx 72k images with 943k questions
approx 10.2k images with 12.5k questions
Visual Question
VisWiz
Vision. Text
8k image and questions
approx 4.32k image and questions
Answering
TextVQa K3
Vision. Text
approx 28.4k images with 34,6k questions
approx 3.1k images with 4.2k questions
images questions
Science A
Vision, Text
approx 4.1 image and questions
approx 2. image and questions
Text Classification
LMDb
88
Text
25k movie reviews.
25k movie reviews.
SST-2
87
Text
67,349 sentences
872 sentences
Image Classification Imagenet-
Vision
Approximately approx 1.28 million images
50k images (50 images per class)
S1
B PITOME Algorithm
B.1 Pseudo-Code Implementation
The pseudo-code for method is provided in Algorithm 1 Here in line 3 is vector that represents energy scores all nodes calculated by the energy function The final output is a MERGE(.) function, which serves as a lambda function that can be applied to any matrix X at the I-th layer. The vector tokens being merged into each token).
vector that contains information about token sizes (i.e, the number of
Algorithm 1 PrToME Algorithm
1: function PrroME(remain token ratio: r, input graph: G(V,E) // Function to prepare for merging
2: & - N -r
// Compute number of nodes to merge Compute energy scores // Identify mergeable and protected nodes // Split mergeable nodes I/ Get edge weights of mergeable nodes // Find closest neighbors I/ Function to perform merging Extract protected tokens // Extract tokens in set A and B // Weighted average I/ Merge tokens I/ Weighted
3: S argsort(E, descending-True)
4: merge, protect <- s 2- k.., k
5: Da. n, + merge(:: 2). memgee ::
6: Emerge +- E(n,)]
7: Ddet & argmax Emerge)
8:
function MERGE(X)
9:
X Xprotected f- X/protect.) :
10:
X1,XB t Xin :..::,nnns.
11:
X1. Xg + MAx x Ng x m min]]
12:
XB f Xg.scatter reduce (d XA, mode = "sum")
13:
XB < ht/mm.scatter. rrducce Dast, mA, mode "sum")
average
14:
return cat(X, pprotectdd XB)
Concatenate and return merged tokens
15:
return MERGE
// Return merging lambda function
B.2 PITOME Complexity Analysis
In algorithm T line the weighted graph is constructed through matrix multiplication, leading to complexity of O (N²h), where h is the dimension of input vectors. Next, the computed energy scores are sorted, which have the complexity of O (N log(N)) Lastly, in line 7, the max operator for selecting the merge destination and the lambda MERGE function, which performs tensor operations based on computed indices, lead to linear complexity. Combining these aspects, the overall time complexity of the PITOME function can be approximated as O (N²)), considering the dominant factors contributing to computational cost. However, actual performance may vary depending on the specific Porrrc version and hardware utilization, with optimizations potentially altering these estimates.
19

---

Palse
500
Tue model
Tuu
400
model
CUP
CLI
400
CLIP BUP
CLIP
(05 15.2m
BLIP
300
203
200
100
100
(a) MSCOCO
(b) Flickr30k
Figure 9: Off-the-shelff performance of all backhones for image-text retrieval task using different token merging schedules.
In the BSM algorithms used by ToMe, after the bipartition of tokens into two sets A and B using odd and even indices, each set has N/2 tokens, it also requires calculating a similarity matrix between tokens in these two sets. This operation also has the complexity of O (N²)). The similarity matrix is then sorted to get the top & tokens in set A with the highest similarity score used for merging, this operation also has the time complexity of O (N log(N)). and the merging procedure the same as our PITOME algorithm. So basically when compared to BSM, our algorithms have the same time complexity of O ( (N*)), although in practice the speed of ToMe a little bit faster than РгTоME (a few milliseconds), but our algorithms give much better trade-off between speed and accuracy. For more details about the BSM algorithms please refer to the ToMe paper[[S].
B.3 Model complexity analysis
In a standard Transformer layer, we have the time and space complexity to be O (N2 + +Nh?
and O (NN2 + Nh). In each layer ith of the model, we compress the number of to- kens down to rN using PITOME algorithms with the complexity of O ((rt-1 layer will enjoy the time and space complexity of O ((r=-1N)hh r' N'2 (r)-1))))) and O ((*=11))2 + Nh) resp. Vision language models like LLaVA directly use output to- kens from VIT encoders. Let be the number of layers in the ViT encoder since we utilize PITOME in each layer in the ViT encoder part; the LLM model will have the time and space complexity of O ((''NvTT + NLLM) + (r' Nvr + NLLM)A²) and O Nyrr + 2 + (f' Nyir + NLLM)) which boosts the inference speed and saves a high amount of memory usage. The speedup could get even more impressive when used with higher batch size and image size. This also applies to models that use cross-attention modules for image text matching like BLIP and ALBEF, in which most of the computation expense comes from to- kens encoded by the ViT model, the time and space complexity for the cross attention layers are O (r' Nvision Ntext h + N2)xth?) and O (r Nvision Nuext + Ntexth resp.
the
C Performance of ToMe with Different Token Merging Schedules
In the original ToMe paper, the authors proposed a merging schedule that involves reducing tokens in each layer by fixed k tokens per layer. However, as illustrated in Figure we showed that this merging schedule suboptimal for off-the-shell performance, and this section provides empirical results to confirm this claim.
In this experiment, we exclusively compare two versions of the BSM algorithms utilized in the ToMe paper: one that preserves a percentage r of tokens in each layer and another that reduces fixed k tokens in each layer. However, for a more comprehensive comparison, we extensively apply these algorithms across 6 VIT backbones (DeiT-T, DeiT-S, DeïT-B, MAE-B, MAE-L, MAE-H) for image classification tasks using the Imagenet- k dataset, as well as across backbones for image-text retrieval tasks (CLIP-B, CLIP-L, BLIP, BLIP2) on FLickr30k and MSCOCO dataset.
20

---

92
use 8 1855
87
Tue
ma3e
model
D-T-0-15
MT-4144
Accurscy
12
70
10
35
40
50
120
FLOPS
FLOPS
(a) DEIT backbones models
(b) MAE backbone models
Figure 10: Off-the-shell performance of all backbones for image classification task using different
token merging schedules.
10a 9b and 9a| it is evident that, given the same FLOPS,, the BSM version that uses the remaining percent r shows a clear ad advantage. outperforming the original schedule by large margin. This gap becomes even more pronounced when benchmarked on large models like MAE-L, MAE-H, and BLIP-2. During the experiment, we also observed that models compressed using the ratio r tend to run a little faster since large number of tokens are removed in earlier layers.
From Figures TOb
D Additional Experiments on Text Classification Task.
This section comprehensively assesses the performance of PITOME against other baseline algorithms for sentiment text classification tasks. We conducted this experiment using the IMDb and SST-2, applying the compression algorithms to the first three layers of the model. To ensure consistency in our experimental results, we used two different backbones: BERT with 12 layers and DistilBERT with 6 layers. Since we only compress the first three layers, in addition to the baselines previously used throughout this paper, we introduced two additional baselines: ToFu-p and ToFu-m. ToFu-p uses BSM to prune tokens instead of merging them, while ToFu-m represents the original ToFu algorithm without pruning.
Table 10: Performance of PITOME versus baselines algorithms when training BERT and Distiled- BERT when retrained from seratch.
Datase
Model
Compress methed
flope
0.8
eval
train spred
Bops
0.75
train speed
flops
0.7
eval
spred
train
ToMe
91.25 (-0.20)
x1.88
x1.14
x1.40
39.
(-2.33)
x2.37
x1.22
x1.56
68 (-3.40
x2.72
x1.30
x1.68
ToFu
x1.40
38.64
x2.27
87.22 4.23)
x2.72
X1.68
BERT
DCT
90.66 (.799
x1.05
X1.12
39.31
2.14)
x2.15
87.26
x2.72
X1.61
DifRRate
89.72 (-1.75)
x1.88
x1.14
X1.40
$7.96
x2.27
x1.55
87.64 (3.81)
x2.72
X1.68
SST-2
ToM0
PiToME
31.01
X1
39.36 (-2.2))
X1.88
X2.37
W6.64 (-1.4)
88.67
$2.25
X1.65
x1.88
(-3.67)
DisildBERT
DCT
87
PiToME
(2..37
(-1.61)
x1.79
92.22
x2.30
91.31 (
x2.77
x2:25
1.04)
92.53
x2.77
X2:33
PITOME
X1
93.27
x2.01
92.74
x2:31
X1.37
K2.5
(1.66111114)
12.33
Tollu
x1.57
92.33 (40.7)
x2.15
12.53
x1.35
DisilaRFET
DCT
(-0.6))
x1.61
<1.30
x1.
x1.79
<1.48
x1.56
x1.77
DifRate
x1.83
x1.55
(-0.4)
x2.15
x1.57
x1
22)
x1.63
PyToME
92.71 (-0.29)
x1.83
x1.43
x1.54
92,55
(-0.45)
x2.15
x1.54
x1.61
92.06
(-9.94)
x2.53
x1.62
x1.33
As demonstrated in Table 10 and Figure II our findings align with empirical results from previ- ous tasks, indicating that PITOME consistently achieves superior performance compared to other baselines. Particularly noteworthy is the performance on the IMDb dataset with large context length, where even after reducing FLOPPs by 80%, models compressed by PIToME still maintain off-the-shelf accuracy above 85%, while other baseline algorithms see the off-the-shelf accuracy drop below 70%. Furthermore, Table 10 highlights that algorithm can also facilitate better model
21

---

learning compared to other methods, achieving high accuracy that closely approaches that of the original model.
E
Proof of Theorem 1
E.1 Sketch of Proof
The proof sketch for Theorem begins by defining coarsened and lifted versions of the original graph G (see Definitions/ I and using the PiToME and ToMe algorithms. The goal is to demonstrate that the spectral distance between and its PrToME-coarsened counterpart converges zero, whereas the distance for ToMe remains bounded away from zero. The sketch proceeds by introducing Propositions and which build toward the main result:
1. Proposition D
establishes upper bounds on the edge weight differences between merged nodes under the PIToME and ToMe methods.
2. Proposition
2 employs standard mild assumptions to relate the cosine similarity among (e) nodes within clusters, demonstrating that the upper bound error ÉPITOMe between the edge
weights of merged nodes in PrToME-coarsened graphs Gp converges to 0, whereas this property does not hold for the ToMe-coarsened graphs 9
Proposition 3 completes the sketch by bounding the spectral distances of the coarsened graphs in terms of the edge weight differences from the earlier Propositions [
Each proposition is proven in detail within the appendix sections following this sketch, Note that Theorem |
immediately follows the following Propositions and 3 which are proved resp. in
Sections and
Proposition 1. Suppose the graphs g% OpITOME and P are coarsened from the original graph by iteratively merging pairs of nodes Ua, and ub, w.r.t. the true partition p!a) (Vod) hels) the PIToME-parition PiItoMe (V (Eeee defined by PITOME Algorithm 1 and the ToMe- (11fe) TaMei s for for: NN..., 1. We assume the following standard
partition [15 [6], ToMe
mild assumption:
(A2). There exists margin m s.t.
cos(Va, vb.) 2 cos(Vn, Ve.), Vua, ((s) Von. vii Vuc, E V Vi + E [s].
(6)
Then, the edge weights of merged nodes from PITOME Algorithm 7 Aand the ToMe-partition satisfy
16
||W :| Wbb..
:]]1 :/b..:]l
S cl
(7)
for some nonnegative upper bounds (6), 8 N, N b....,97 n + defined as follows:
2(1 cos(Ua,, v) Va E (()) ub, E V Vi E [s], 3(1 3)
(())
(8)
Va v(()) vb, v(+) x [s].
Proposition
We assume some standard mild assumptions:
811
Lestr
71
254
116
263
201
262
14
080
135 309
315 303 331
Figure 11: Off-the-shelf performance of various algorithms on the text classification task.
22

---

(AI). Ploos((a,,> [b.)) + Vea E vooi Vos, E Voo [s].
cos(va, vb,) ) 2 cos(ve, Ve.), Vea E V(() Yes, Vis Vvc, E Vo) vi Hi [s].
(A2). There exists margin
(A3). There is an order of cardinality in the true partition, without loss of generality, we assume N( N2 ... N where N( 1Vo Vi E (s).
Here (.) stands for the expectation of the random variables that define the random events M == (va, Vlla, Ub, Vite [s]], indicating that the two merged nodes belong to the same true
partition Vor Given the (()) defined in equation (8). we obtain
(s) The upper bound error <PITOME between the edge weights of merged nodes from PITOME-
coarse SPITOME graphs converges to O, i.e.,
(a) PPTTME + (E(co(UV,, vb,)) for any N.....,
(e)
2. The upper bound error ETMee between the edge weights of merged nodes from ToMe-coarse (n)) ToMe graphs converges non-negative constant C(5), with high probability that C(+) > 0, i.e.,
'ToMe
(s)
any + ((s) and (P(((()) ) > 0) > O as (I,, 1, for any 8 = N,
1.
g(s) Proposition 3. Suppose the graphs G6 DpiToME: and ToMe coarsened from the original graph G by iteratively merging pairs of nodes Va, and Ub, w.r.t. the true partition pba) (v he(s the p(e) PIToME-partitinn PPITOME (V (VE))) defined by PITOME Algorithm 1 and the ToMe-
partition [75 16], p(s)
(V/4) ToMeitee heesss for ,....,,2 1. If the edge weights of merged nodes
TaMe =
satisfy
[| :l [b... :]]l < (s))
for some nonnegative upper bounds e(*), N, I..... n 1. The spectral distances between the original g = N) and the PrToME-coarse and ToMe-coarse PpToMe graphs are bounded as follows:
3N a+1
max ((n) ( SD(G, (lm)e) ( <
Σ c(,).
s=N
E.2
Proof of Proposition
We want prove that the edge weights of merged nodes from PITOME Algorithm and the ToMe-partition [15 16 satisfy
[ W/b.. :]II < cl))
for some nonnegative upper bounds c(*), N, N I...., n
Let us start with the simplest case, where we suppose the graph Ge is coarsened from 9 by merging one pair of nodes and using PIToME Algorithm [ and the ToMe- toMeepartition. We then
demonstrate that the edge weights of the merged nodes satisfy certain conditions (for more details, refer Appendix E.
[[a,:] [i:::]W[bppp :Il11 S c for nonnegative upper bound
Recall that the graphs g g(a) PPITOME and gls) are coarsened from the original graph G by iteratively
merging pairs of nodes Va, and Ub, the partition Pp(*) (v(()) >e([s)- the PiToME- PrToME-partitin
PITOME (V Die()) defined by PřTоME Algorithm and the ToMe-partition [15 16].
[V P JoMe ToMei hiels for s = N...., n++ 1. By iteratively applying the merged 2-nodes inequalities obtain the desired upper bound as follows:
| (Waa,,1 :] Wbb, :]I1 < (s)), for all N, -I...,, +
23

---

where
(6)
2(1 cos(ea,, (2a, (b 3(1 3)
,b.))
if va. if ta, Vos vb Vog i i+ ú+j= j [s].
Vili ub V i [s]
E.3 Proof of Proposition 2
Recall that in equation
( of Proposition
1 we defined c(+), for 8- N, N - -1,, .I..., 1, follows:
2(1 cos(va, (b.)) if ca. Vile) lb, Vil i [s]:
3(1 ())
if Va, vi(e) Ub, Voj i + [s].
Recall that we defined E (-) as the expectation the random variables that define the random events
M fua, Vo6e lb, Vil i [s]}, indicating that the merged nodes belong to the same true partition (/s)) Using the definition and the linearity of expectation, we have
(c))) 2[1 E (cos(ta, tb, )) + 3(1 - 3) (1(1-PP(AA) P(M)))).
(10)
Under Assumptions (A2) and (A3) and the eneryy-based merging mechanism of the PITOME
algorithm, we can verify that ( 1 via Lemma which is proved in Appendix E.5.2 Refer to Lemma 3 for the ToMe approach (proof Appendix E.5.2), noting that there exists a scenario
where the random event M does not occur, leading to PP(()) < 1. This leads to the desired results.
Lemma 2. For the PITOME approach, it holds that ( 1, i.e. there exists true partition
V i i [s], such that Va, Visi Uh, V
Lemma 3. For the ToMe approach, there is case where the random event (x) therefore ((M) <.
ab does not occur and
E.4 Proof of Proposition
Let us start with the simplest case. where we suppose the graph Ge is coarsened from Ç by merging one pair of nodes va and th. We can then prove the following property: If the edge weights of merged nodes satisfy
| - Wib, Se
then the spectral distance between the original and lifted graphs is bounded by
(11)
Proof of the 2-node triangle inequality [7] Indeed, since the coarse graph 9. coarsened by merg- ing pair of nodes v. and Vb. the edge weights of the lifted graph Gi can be formulated as: W + [[.b]]
if i, {a. 6).
(a. w [
if i E {a, b} and j & {a, b}, if i & (a, and j E (a,b), otherwise.
W W
(12)
W
Here we use the fact that the adjacency matrix elements of Gi are given by
Wi[i.5] = Σv,e,, Enyev, W
where vs V,, and 0j E V,.
(13)
The corresponding node degree of Gi is
da da
if (a,
di
(14)
d;
otherwise.
Using the result from Lemma
4 bound on the eigenvalue gap between À and X via the
perturbation matrix L
L
D Dj + W - W as follows:
A
Ar
Σ
D4 - Aul <
El S N
E
(15)
24

---

Here the last inequality follows from the upper bound of the spectral norm | of [94], and we defined E /a max; E, Eli which simply the maximum absolute row sum of the matrix, and Elj1 = max; E; Cilll. which simply the maximum absolute column sum of the matrix.
Lemma 4 (Perturbations of eigenvalues: Weyl's inequality from 195). Let L E RN and L E NNXN be symmelric malrices. Then for all 1,..., N.
Inxx i=1..., N
(L)) - (L) S L
(16)
where [L L is the induced 2-norm of L: L.
The equations
and
yield the following identities:
W
if E {a,b). if E {a, by and j & {a, b),
Woo.]++Wb.ll
W[i
Wi|i.]] - -[
Wh.a Wib
W
if & fa, and {a.b).
otherwise.
(17)
and
d4 tod if (a, otherwise.
Dii - Di
(18)
0
Now we want to prove that EEllc S c and |Eil1 S c. Let us first focus on the first term | |E|xc
max; E; E[i.j]l- Via the triangle inequality, we have
Ell S D || W
(19)
Then, again using the triangle inequality and the assumption of Proposition upper bound on the first term of the equation
we obtain the first
(19) as follows:
dg
+ db
||D
Di max Σ D
Dr[i,
max iE (E(a))
d;
2
dg
dg
da db
dg
2
N
W
Waj
Σ j=1
W bj
S
W(a,
Wbb
1=1
j=1
[[
W[b -11
(20)
2
For the second upper bound term from the equation 19
we consider two cases for each index
i= 1, ... N: i {a, b) (Case f) and i {a,b) (Case 2).
Case Assume that E {a, 6}. Since a and have the same role, we can take i = a without loss of generality. Using the equation (7). it holds that
[W W1 = max :E(a,))
Σ
W - Wii.il
2W + W b, b)
3W (W(a,
Wía, + W(b
b
W W(a
W b,
Σ
+
4
2
ja(a,))
(W W W(a b)) + 3(W
[a, W ((a
(W a] b), + (W(a, b] W B)) 2(W(,, W(a
Wía,j] W
j (a,b)
25

---

Therefore, it holds that
3 Wbb
IW W cl
W a.
W a] W/a
4
4
W|a
W/a 6||
w [a w bJ]
W[a,
6 bj]
Σ
W|..j]
bbb (using triangle inequalities)
jk|a.b)
W bj - W/b b|] + W| Wia bl +
1
Σ W[a,j] W(6,i]
2
jK(o,b)
[W[a, w/b bl| W[
Wi, [laaaaa-a,bBlll
Σ
W[.
W
jE(a.b)
[a,: Wlb S.
(21)
Case Assume that i $ {a, b). Using the equation 17 obtain
[W W/ = max
Σ
Wili,j]
W [i,ll
s (0.b)
JEV
W (i, a) + b
W 7, a + W
Wii
W
2
2
W a|
6
W a|
W(i,
+
2
W|i, a]
W b]|
W[o,:]
Wib, =II1 S.
(22)
Combining
2T and 22
we obtain
W W cc
This leads to
3 2
E
when using the inequalities and (20). Similarly, we can show that E||1 Jcc. Therefore, the equation (15) leads to the desired claim as follows:
3N 2 6.
3 3
a Arll N
Recall that the graphs = G and g(a) are coarsened from the original graph & by iteratively merging pairs of nodes ve, and Vb, w.r. the true partition p)()) {V("" Heess) the PrToMe-partition PPITOME (Vie) )eee) defined by PIToME Algorithm and the ToMe-partition 15
plo) (Vile (ree)) for N,..., 1. By iteratively applying the triangle inequalities ToMe
(n)) 11. the spectral distances between the original g gi and the PiToME-coarse SPTTMMe and
ToMe-coarse g(n) graphs are bounded as follows:
n+1
max(SD(G, of SD(G, gff)) (oMe))
} S
max (SD G (S((G()) ((
3N
++
(+)
2
8
E.5 Proofs of Technical Results
E.5.1 Proof of the merged 2-nodes inequality
Recall that there exists the graph Gn coarsened from the original graph G by merging pair of nodes Ua, and th, w.r.t the true partition Po = (Vor heeee- Then, we have V Von U Vb2 U... U Von. where = N - 1. We also note that the energy score E. of node v, is calculated using the following
26

---

equation:
Eu Ea= N
Σ fml(co((ua ub)), fm(x) bEN(a)
- -(z a(eexp(< m) - 1)
if 2 m
(23)
otherwise
Inspired by the construction of the function fm in equation 23 and according to Assumption (A2) in the inequalities (6). we can replace the smooth term a (exp(( m)) 1) by a constant 3 for simplicity. More precisely, if the nodes Va and Us are not considered true neighbours, i.e. their cosine similarity less than the margin m, then
simplify the expression follows:
(a:: Ub) = ==
sup
((exp(cos(1; 02) - m) 1) <0.
(24)
VuEVor,evEeo [
To check the inequality 9 we examine the following term
[[ - Wbb. :1l11
in tWO cases:
Case I. If two nodes va and belong to the same true partition, say for example, Vor, i [N], then since n = N-1. 1, we have Vn= = {Va, }. Therefore, we can expand the previous I 1-norm as follows:
[W. w(b,:ll1 Σ W/a, k]
W[b, &]]
=
Σ
Wla, k] 1|, k|]+ Σ
W|a, Wlb, k]]
VoV
d E Von
= [[a. - W all + W a. bj bb
= 2 cus v=)l
(25)
Case 2. If va E Vor and v6 Voy such that + j. i,j [N]. Since n -N -N11, 1, we have either
Vor = {Wa, Uns }, Voj = {2r} (Case 2.1) or Voi = {2a). Vos fer, 2aj (Case 2.2). Let us first
consider the Case 2.1, then holds that
WWa, Wlb = Σ W[a k] Wbb
N Σ
Σ W Wlb, x]|
Σ
[[a, W[b, k]]
[W k]
Wlb, k]]
E
2y gov Ux VVo
[W(a a] a[b + W1a,, 0i] [bb, 0i]l + [W bj
W[b
= (1 - B) + |1 - cos(Uar Vo:) - (1 B)1 + (1-3)
= 2(1 () + coos(va; voi) B1 < 3(1 - B)-
(26)
Now, let us first consider the Case 2.2, then it holds that
W[a, wb.
Σ W k]
W[b k]]
N
N
N Σ
= Σ
W k] W1b + Σ
[[ k] W[b, A]]
[W k] - Wlb, k]]
e.VVo.
V Vos
Vi Voo;
[W(a,u a] W(b,a] + W[a, 0j] Wlb, jil + [W(a,
[[bbb]]
= (1 - () + |1 -cos(2a: U0j) (1 - B) + (1 (1-B)
= =2(1 - 3) + cooosVa (oy) - $ < 3(1 :3)
(27)
Combining the previous equations 25 (6) and (7 we have
[2]1 cos(va, vb)l
if vas Up Vos Vi E [N], if w. Voi, up E Voj, vi # j E [N].
||W w[b.:]la < 13(1 ()
(28)
27

---

E.5.2 Proof of Lemma 2
Recall the following Assumptions (A2) and (A3):
(A2). There exists a margin m s.t., cos(Va, vb.) 2 m > cos Vo.), Vva, E Voll Ver, E Vil Vee, E Vo Vi + E [s].
(A3). There is an order of cardinality in the true partition, without loss of generality, we assume N(*) o( ... N! where N²(0) | Vi
[s].
In PIToME approach, using Assumption (A2), given any two nodes Va, E ( Ub, E vod , jije E
[s]. the energy scores Ea, and Es, of nodes va, and th,,, respectively, are simplified as follows:
Ea,- = N
Σ
Ia(cos(Va, vn,)), where fm(x)= -
if x 2 m
if < m
o, (((
cos(vas: ve,) N - N²
N²(5) m + (N N
1
Σ
N B
(29)
N
N
Vey EVI
N - N7(0)
N₂00 + (N N/
Eb, - N
1
Σ
COS(Ub,, vo,)
(30)
N
EVI
Roy
N N..
Given the choice of the universal margin as follows: m max
:1 < E [s]
it holds that
Es, 2 Es,- Indeed, this is guaranteed as long as we have
N m + (N N1 N60) + (N - N(1))8
(31)
N
This is equivalent that m
N + (N N/ (N 2B No + (N(() -N
Nr(0)
(32)
N(0))
N/00)
N7
Using Assumption (A3) and this choice of universal margin m, holds that
Ea, 2 Es,, for any Va, via) Vb, Viy) ; < [s].
(33)
Recall that in PrToME approach, where we defined two set A and B with |A| = [B] = k as follows:
the ordered energy-based for the bipartite soft matching
A
{uf, ug... ....... - B {og, of..... ... }
(34)
where the nodes of E [2k:]. are sorted in decreasing order based on their energy scores, iee, Eug > Eegg, Vi E [2k- -1.
We return to the proof of the Lemma by contradiction. Assume that va, E (v()) Ub, E V1(g) .
j E [s]. Without loss of generality, we assume that Ua, = of E vot and N7(0) = [ > 1. Note that PiToME algorithm selects tb. B such that
vb. arg max U,, EB cos(Ua,, Vec).
This is equivalent that for any Uc, B, it holds that:
cos(Va,, Vo,)) S max Un, EB cos(va,, Ve,) = cos(va, , Ub,) < m.
Assumption (A2) implics that vg. & (/(5) Vi E [k]. Since we have N((0) [
1, there exists at
least one node in A n Vi(o) say for example ug. Using (34), we have Eug 2 Eug. which contradicts
33 where we have Eng > Eng since vg 1/(a) and ug E Vi(o) . > 1.
F.5.3
Proof Lemma
On the contrary, in the Bipartite Soft Matching algorithm from the ToMe approach 15 the authors divide the tokens into two distinct sets A and and merge the top similar tokens using some partitioning style like sequential, alternating and random without considering the ordered energy-
28

---

based Bipartite Soft Matching like ours. This leads to case where the random event ab does not occur and therefore P(M ab 1. Indeed, this case happens when all the nodes from the true partition V (x) are divided into the same set A. Therefore, the Bipartite Soft Matching algorithm has to choose and select the node lb, E 1o .j > 1, for merging. Actually, this case arises when all the nodes from the true partition Do1 are distributed into the same set A. Therefore, the Bipartite Soft Matching algorithm has to select the node vb, Vo4 :J > 1, for merging.
Token Merging Outputs Visualization
To better illustrate the effectiveness of PITOME, we have incorporated many visualizations show- casing examples randomly sampled from the MSCOCO dataset, as depicted in Figures 12a this analysis, we utilized the BLIP backbone and configured the reduction percentage to 0.85. These visualizations portray the final representation of all remaining tokens the last layers. Notably, tokens outlined with bolder cyan borders signify higher attention scores from the classification (CLS) token. Apparently, unlike ToMe and DiffRate, PrToME adeptly approximates the spectral spectrum of the original token space, thereby preserving the distribution all tokens. Consequently, PITOME demonstrates a lower level of information distortion due to reduced mis-merged tokens, thus retaining attention maps for critical information in the final layer. As illustrated in Figures 12a 26 |2c 12e the attention map in the final layer of the model compressed by PIToME exhibits the closest resemblance to that of the baseline model.
G CpenChat with Compressed VA-1.5 Model
This section is dedicated to showcasing sample responses of LLaVA-1.5-7B when compressed using different algorithms. Here, we set the compression rate to r = 0.9 for each CLIP layer. All sample answers are given in tables 11. false information given by the model. From these sample answers, algorithm PITOME not only facilitates quicker model responses but
13 12
Texts that are highlighted by blue color indicate evident that, unlike other
BSM-based approaches, also retains its capability to recognize objects, understand contextual information in the image, and provide correct answers closely aligned with those of the original LLa LLaVA-1 VA-1.5-7 model.
29

---

Figure 12: Visualizations using random images sampled from the MSCOCO dataset.
VIT-B 384
Pi (ours)
ToMe
DintRase
(a) A white dog catching a novelty flying disc a competition.
VIT-B 384
PiToMe (ours)
ToMe
DiffRate
(b) A woman riding horse jumping it over obstacles.
384
PiToMe (ours)
ToMe
Dietate
(c) Three diffcrent motorcycle couples riding down a road.
M
VTTB 384
Pi (ours)
ToMe
DinRate
(d) A man holding tennis racquet tennis court.
PiToMe (ours)
ToMe
DiftRate
group people who are around a kitchen counter.
30

---

Table 11
USER: Describe what you
Model
Answer
LLaVA-155-BB
the image, a busehall game is taking place with a batter standing at home plate, holding a baschall bat and preparing to swing. The catcher is positioned behind the batter. ready to catch the ball if the batter misses. There are several other players on the field, including teammates and opponents, all focused on the ongoing play. Some of the players are standing closer to the hatter, while others spread out across the field. The scene captures the excitement and anticipation of crucial moment in the game.
LLVVA-15-7BB PITOME
image, a baseball player in middle of swinging baseball bat. attempting
ball during a game. There are several other people in the scene, some of whom are wearing baseball gloves indicating that they are also participating and the action of the batter suggest that this is an exciting moment the game, with the batter trying make contact with the ball potentially score run for their team.
the game. The presence multiple players
In the image, group of people is gathered on a baseball field, with some of them holding haseball bats It appears that they either practicing or participating in a baseball game. There are several people standing in various positions on the field, and some of them are closer to the foreground while others are further away. The scene captures the excitement and camaraderie often associated with baseball, as people come together to enjoy the game and improve their skills.
LLaVA-L.5-7B+ ToFu
In the image, there is baschall game in progress with multiple players on the field. One player holding baseball bat and in the process swinging it, likely attempting
the ball. Another player is holding a basehall glove, ready eatch the ball it
There several other
players on the field, some of them wearing baseball gloves as well A bench can be seen in the background, likely for players to sit on when they are not actively participating in the game. The scene captures the excitement and action of a baseball game.
LLVVA-1.5-7B DiffRate
In the image, group of people is playing game of baseball on a field. There are several players the field, with some of them holding base- ball bats and wearing bascball gloves. The players are actively engaged in the game, with one player holding basehall bat and another player wearing baseball glove, ready catch the ball. The other players also positioned around the field, either waiting for their turn to bat or preparing to field the ball. The scene captures the excitement and energy of a live haseball game.
31

---

Table 12
USER: Describe what Answer
Model
LLaVA-L.5-7B
In the image, a man is standing folding chair in the back of yellow taxi cab. Hc holding blue shirt, possibly drying it preparing put on. The taxi driving down busy street with multiple cars around it, including another taxi in front of it. The man's position on the chair and the presence of the shirt suggest that he might be street vendor or worker who is using the taxi as mobile workspace.
LLaVA-1.5-BB+ + PIToME
the image, man is standing on back moving car, holding a clothesline with clothes hanging from The car appears to a taxi cab, man is wearing yellow shirt. scene seems to taking place in husy city, there are multiple cars visible in the background. The man's unusual activity hanging clothes from the hack of moving likely attracts attention and curiosity from passersby.
LLaVA-1.5-7B +ToMe
The image shows a man standing on the back a taxi cab, holding a large umbrella. The taxi is driving down a street, and the man appears he using the umbrella shield himself from elements. In addition to the taxi, there are several other vehicles in the scene, including a truck and car The man on the taxi is the main focus of the image. and his actions suggest that he is trying protect himself from rain other weather conditions.
LLaVA-I.5-7B+ ToFu
The image depicts a busy city street scene with a man standing on the back of a truck, possibly performing stunt or participating in a pa- rade The truck is positioned in the middle of the street, and the man appears to the main focus the scene. There are several other people in the image, some of whom are walking or standing near the truck. Additionally, there are multiple cars parked or driving along the street, and a traffic light can seen the background. The overall atmosphere suggests urhan environment with lively and hustling atmosphere.
LLaVA-1.5-7B DiffRate
The image features a man wearing yellow shirt, standing next to yellow cur, He appears to be holding onto the possibly for support to steady himself. The car is parked cars visible in the background. In addition to the man and the car, there other people in the scene, one standing further back and another closer to foreground A handbag can also he seen placed on the ground near the center of the image.
street, and there are other
32

---

Table 13
wWW Krajicek.nett
Describe what happening? Answer
USER:
Model
LLAVA-155-BB
In the image, a woman is riding horse and jumping over hurdle, which is a part of an equestrian competition. The horse and rider are in the middle of the jump, showcasing their skills and coordination. There are several other people in the scene, some of whom may be fellow competitors or spectators. The presence of multiple people and the focus on the horse and rider suggests that this a competitive event or practice session.
LLaVA-1.5-7B PrToME
In the image, person is riding horse while jumping over obstacle, likely during an equestrian event or competition. The horse and rider are in the middle of the jump, showcusing their skill and coordination. There are several other people in the scene, some of whom might be fellow competitors, trainers, or spectators. One person is standing close the rider the horse, while others are scattered around the area. The overall atmosphere of the image suggests exciting and challenging equestrian event.
LLaVA-1.5-7B +ToMe image, person riding horse jumping over an obstacle, possibly hurdle or small hill The horse and rider are the middle the action, showcasing their skill and coordination. The scene captures the excitement and challenge of equestrian sports, such show jumping eventing.
LLaVA-1.5-7B + ToFu
In the image. a person is riding horse while standing a corral. The horse and rider are positioned near fence. which could be part of fenced-in area stable. The scene captures the bond between the rider and horse as they interact and move together within the corral.
LLa VA-15-- DiffRate
In the image, there two people riding horses likely participating in horseback riding lesson practice session. positioned next to each other, with one horse and rider on the left side and the other horse and rider on the right side of the scene The riders are wearing helmets for safety, and the horses appear to be well-trained and cooperative. The scene captures the essence of a horseback riding activity, where the riders are learning to control and communicate with their horses effectively.
horses and riders are
33

---

NeurIPS Paper Checklist
1. Claims
Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Question:
Answer: [Yes]
Justification:
We provided experiments to support our claims.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how be expected to generalize other settings.
much the results
is fine to include aspirational goals as motivation as long is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification:
We included it at the end of the paper.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification. asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low images are taken in low lighting. Or speech-to-text system might be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach address problems of privacy and faimess.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question:
For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
34

---

Justification:
All assumptions are already stated.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [Yes]
Justification: we provided experiment descriptions in the main paper and appendix. Further- more, we will release GitHub implementation if the paper is accepted.
Guidelines:
The answer NA means that the paper does include experiments. If the paper includes experiments, No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how reproduce that algorithm. (b) If the contribution is primarily
model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome deseribe the particular way they provide for reproducibility, In the case of closed-source models, it may be that access to the model is limited in some way (e.g., registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
35

---

Answer: [Yes]
Justification: We will publish the code when the paper is accepted or through an anonymous link if some reviewers ask for it.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips cc/
public/guides/Codese/ wwt.oooeeesiiiiioooooiooiooo for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to to reproduce the results. See the NeurlPS code and data submission guidelines (https
ssicnyolicy) for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification:
We provided details for experiments in the paper.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment Statistical Significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
Justification: We conduct experiments on diverse datasets and follow the protocol used by previous works for fair comparisons.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
36

---

It should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative enror rates).
If error bars reported in tables plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
Answer: [Yes]
Justification:
This information is included in our results.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary failed experiments that didn't make into the paper).
9. Code Of Ethics
Question: Does the research conducted the paper conform, in every respect, with the NeurlPS Code of Ethics httppp////.errre...coo/o//////aa
Answer: [Yes]
Justification: Our paper follows the NeurIPS Code of Ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special cireumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., if there is special consid- eration due to laws or regulations their jurisdiction..
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification: Our work helps to reduce the carbon footprint when training large models using ViT. There no negative societal impact.
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
37

---

The conference expects that many papers will be foundational research and not tied particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility of MI..
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: Our work does not pose such risks.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Lieenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [Yes]
Justification: We have properly cited papers and resources used in experiment.
Guidelines:
The answer NA means that the paper does not existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
38

---

If this information is not available online, the authors are encouraged to reach out to the asset's 's creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: Our paper does not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets,
Researchers should communicate the details of the dataset/code/moodl as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification: We don't have experiments involving crowdsourcing or research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According to the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification:
We do not involve crowdsourcing research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and expect authors to adhere the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
39


Reviews:
[{"review_id": "YILPKVJiYA", "reviewer": "Reviewer_zfJf", "summary": "This paper proposes a novel method called PITOME, which enhances the efficiency of Vision Transformers (ViTs) by merging tokens in a way that preserves crucial information. Unlike previous methods, PITOME uses an energy score to prioritize and protect informative tokens while merging redundant ones. This approach reduces the computational and memory requirements by 40-60% with minimal impact on accuracy. PITOME achieves superior performance in tasks such as image classification, image-text retrieval, and visual question answering, demonstrating its effectiveness and robustness compared to existing token merging techniques. Furthermore, it theoretically preserves the spectral properties of the original tokens, contributing to its efficiency and performance stability.", "questions": "1. In Figure 11, PITOME's token merging appears unreasonable in some cases (e.g., the tennis racquet example). Could you provide a deeper explanation or justification for these visualizations and any potential improvements to address these issues?\n2. The mathematical derivations and proofs are quite complex and impact readability. Are there ways to simplify these explanations or provide more intuitive summaries of the key points to improve accessibility for readers?", "limitations": "The authors have acknowledged some limitations of their work and provided suggestions for future research directions. The paper does not explicitly address any potential negative societal impacts. Given the focus on efficiency improvements in Transformers, the primary societal impact would likely relate to the broader implications of making these powerful models more accessible and efficient.", "rating": 5, "confidence": 5, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "1. The introduction of the energy score metric for token merging is a novel idea that addresses the limitations of previous methods. This innovative approach effectively distinguishes between informative and redundant tokens, ensuring the preservation of critical information during the merging process.\n2. The theoretical foundation for preserving the spectral properties of the original token space is a unique contribution. This aspect of the work sets it apart from existing methods, which often do not consider the impact on the spectral properties of the token space.\n3. The paper provides extensive empirical validation across multiple tasks, including image classification, image-text retrieval, and visual question answering.\n4. The theoretical analysis that supports the empirical findings enhances the overall quality of the paper. By demonstrating that PITOME preserves spectral properties, the authors provide a solid theoretical justification for the observed performance improvements.", "weaknesses": "1. The proposed method, PITOME, does not show significant improvement over the baseline, particularly ToMe, in many tasks. The empirical results indicate that in some cases, PITOME's performance is only marginally better or even comparable to existing methods, which raises questions about its practical benefits.\n2. As shown in Figure 11, PITOME fails to outperform ToMe in visualizations, and in some instances, the token merging appears unreasonable. For example, in Figure 11(d), the merging around \"a tennis racquet\" is poorly executed, leading to doubts about the method's effectiveness in preserving critical details.\n3. The paper includes extensive mathematical derivations and proofs, which significantly impact its readability. The dense mathematical content makes it difficult for readers to quickly grasp the core contributions and the practical implementation of the proposed method.\n4. The paper primarily focuses on improving ToMe by addressing its token merging strategy. While this is a valid research direction, the scope of the problem tackled is relatively narrow. The significance of the improvement may not be high enough to warrant extensive interest or application, as it addresses a specific aspect of an existing method rather than introducing a fundamentally new concept or problem.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your valuable feedback and for recognizing the strengths of our work. We appreciate your thoughtful comments. We will now address each of your concerns individually.\n## 1. Performance comparison with Tome\n\nWe would like to emphasize that PiToMe demonstrates significant improvements over the baselines, particularly ToMe. We acknowledge that the condensed presentation of experiments in the paper might have made it difficult to discern the performance gains of our method. We highlight the performance gains of PiToMe over ToMe as follows:\n\n- Image-text retrieval: At a 60% compression rate, PiToMe outperforms ToMe by a margin of approx 11% for recall score at top 1.\n- Visual Question Answering: With 50% compression rate, PiToMe maintains a more stable performance drop below 0.05% while ToMe's drop exceeds 1%.\n- Text classification: PiToMe achieves a better trade-off, compressing over 60% of tokens with accuracy above 90% (about a 2% drop) and over 80% of tokens with accuracy above 85%.\n- Image classification: PiToMe saves 40-60% of FLOPs, with an average performance drop of 1.4% compared to 2.6% for ToMe.\n\n## 2. Figure 11\n\nWe kindly argue that a misunderstanding might cause the observation that the merging is unreasonable. For clarity, we discuss how we generate these visualizations and then provide a definition of good token merging:\n\n- Implementation: Tokens are represented as grid boxes with black borders, colored by the mean color of the pixels they cover. Tokens with higher attention scores will have a bolder cyan border. During the merging process, result tokens will have their colors replaced by the mean color of all the merged tokens. If merged tokens are adjacent, the black borders will be removed.\n- Good merging criteria: Objects represented by a small number of tokens should be preserved, while larger objects with repeated textures, such as background areas, can be considered for merging.\n\nIn Figure 11d, we observe that PITOME effectively minimizes information distortion by preserving important tokens representing \"the tennis racquet,\" \"the man,\" and the \"Adidas logo\" while merging tokens that contain redundant information representing the background. Despite some mis-merged tokens in the background regions,  PITOME largely preserves the distribution of all tokens. This is illustrated by the attention map, which closely resembles that of the original model.  On the other hand, In ToMe, there are several wrongly merged tokens; for example, all tokens representing the “tennis racquet\" are merged into a single token. Similarly, for the “Adidas logo”. Also, ToMe merges tokens representing the man's arm and the white skirt with background tokens, which can be seen from the resulting false color.\n\n## 3. Mathematical derivations and proof\n\nThe theory section, with mathematical derivations and proofs, is intended to show the spectrum preservation property of a graph built based on merged tokens using our method compared to the original token graphs in ViT. To improve readability, we will emphasize the key steps in deriving our theoretical results and provide high-level summaries in the final version.\n\n## 4. Scope and significance\n\nWe focus on ToMe because it pioneered this line of research, making it a prime candidate to demonstrate our theoretical results. To address the reviewer's concern, we first provide a comparison table, below\n\n| Method | Targeted architecture | Description | Weaknesses |\n| --- | --- | --- | --- |\n| ToMe / ToFu | ViT | BSM with odd &even indices partitioning  | risk  damaging tokens in later layers |\n| DiffRate  | ViT  | BSN with partitioning based on attention score from [CLS] token  | Tightly coupled with the attention scores of classification task and performs poorly on several tasks  |\n| PuMer  | VL models  | BSM+Cross model guidance   | is not able to be used for modal-independent models like CLIP, and is tightly coupled with a vision-language model |\n| CrossGET  | VL models | CGSM + Cross Model guidance | is tightly coupled with vision-language models and is sensitive to token distribution |\n| DCT | Language models | used the FFT operator to filter out high frequencies with low amplitude  | Perform poorly in the vision domain |\n| PITOME | Transformer-based   | PiToMe identifies large clusters and partitions them based on the ordered Energy score of each token. Thus, it is robust again token distribution and can be used for any Transformer-based architecture |  |\n\nWe summarize our contribution:\n\n- Conceptual novelty: We introduce a new concept called *energy score*. When applying this into other applications like LLM, 3D point clouds, video processing, or PDEs, it could open new research directions for designing an optimal energy score that captures specific underlying data distributions. Furthermore, energy minimization theory has been well-studied in fields such as chemistry and physics. Thus, we believe this will pave the way for a new research direction in these fields.\n- Theoretical results: Our theoretical results provide a solid foundation for understanding and applying the energy score concept, offering valuable insights for further research and development.\n- Extensive applications: To demonstrate the versatility of PITOME, we provided extensive experiments for multiple scenarios (image image-text retrieval, image classification, text classification, and VQA using LLAVA-7B and 13B). Furthermore, we compared our method with SOTA compression models in each specific downstream task, showcasing the broad applicability and effectiveness of our approach. Moreover, PITOME’s accuracy can also benefit from existing techniques (differential merging schedule, cross-modal guidance, etc.) to improve its accuracy.\n\nMost importantly, due to the widespread use of Transformers and the associated high computational resources required, significant efficiency improvements can lead to substantial resource savings and open up new applications.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "HTv0RVgNv0", "reviewer": "Reviewer_jrpm", "summary": "This paper proposes a new strategy for reducing the number of tokens used by a vision transformer by merging similar tokens without. Such methods are very sensitive to the type of clustering/partitioning used on the tokens. The proposed approach, `PITOME` explicitly identify highly informative tokens, which should be kept out of the merging process.\n\nMore specifically, the tokens are place in a graph where each node corresponds to a key embedding and the edges are the cosine distance between said keys. Based on this graph, an \"energy\" is computed for each token, capturing how mergeable they are. Only the top $2k$ are considered mergeable, while the rest is preserved. The actual following merging step follows a similar procedure as previous token merging methods:\n\nIn summary, an \"energy\" score is computed on each token, using their key embeddings as base features. Using these energy scores, `EPITOME` draws itself apart from other merging techniques such as `ToME` in two ways;\n - explicitly exclude some tokens from the merging process\n - split tokens across the two sets $A$ and $B$ for bipartite matching as to maximise the change of max", "questions": "- I didn't fully understand the role of **Table 2**: isn't `PITOME` agnostic to the choice of the architecture ? it would send a stronger message to combine `PITOME` with various backbones, rather than compare it to different architectures.", "limitations": "there is a limitation section discussing some current drawbacks of token merging methods in general", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "- The proposed method is thoroughly evaluated on image, text and image+text tasks\n- Generally, `PITOME` achieves higher accuracy while preserving the expected number of FLOPs and memory usage\n- the issues addressed by `EPITOME` are well explained and motivated.", "weaknesses": "- Generally, the **experiments section** is really hard to parse:\n  * the figure placement is a bit all over the place\n  * some results would benefit to be moved to the appendix; for instance, in my opinion, the trade-off curves are much more informative than the tables\n  * some figures are hard to read (Figure 3) (e.g. small captions, overlapping curves due to the y/x axes scales)\n  * ablation experiments are much too condensed \n\n- In terms of ablation, there is little discussion about the term $m$ when computing the energy score: It seems to be an important hyperparameter as it impacts the \"merge ability\" of the tokens as the layer depth increase. Since `ToMe` and other related work are presented as having a lack of robustness to the token splitting strategy, it would be interesting to also show how robust `PITOME` is to this hyper parameter.\n\n- Some claims didn't seem substantiated enough to me\n  - e.g. line 120 *\"`PITOME` remains robust to token partitioning strategies\"*: However `PITOME` uses a specific token partitioning algorithm. And the ablation on it (random split in Table 1) show that it actually suffers from a different portioning\n  - line 276. *\"We contend that this improvement stems from the merging of less significant tokens in PITOME potentially enhancing the robustness of the language mode\"* -> this seems like a very vague hypothesis which in my opinion does really need a justification to begin with, since some other merging methods also outperforms the baseline. It may as well be a consequence of the noisiness of question answering datasets.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your thoughtful feedback and for pointing out substantiated claims. We will now address your concerns one by one.\n### 1. The experiments section is hard to parse\n\n We will address these concerns in the final revision using the additional page. This will allow us to provide more details about the experimental results. Furthermore, we will move some less important parts to the appendix. For example, in Figure 3, we will remove redundant space at the bottom of the top-row figure and the top of the second-row figure to increase the size of the curves.  Regarding the ablation study, we will include more detailed descriptions for each setting and provide an analysis of their impacts to improve clarity.\n\n### 2. Discussion about the term $m$ in the ablation when computing the energy score\n\nWe acknowledge that the ablation study for $m$ is a valuable addition to the paper. To support readability, we include Figure 1  in the global rebuttal to visualize the impact of $m$ when experimenting with multiple margins $m$ on different tasks using various thresholds. From figure 1, it can be seen that, in both tasks, the adaptive version $m=0.9 - 0.9 \\cdot l_i/l$ achieves the best results. While models with fixed $m$ tend to have the accuracy drop sharply when $r$ is lower than some threshold. The reason might be as the token space becomes more spare in deeper layers, PiToMe with fixed $m$ will likely assign the same energy score to every token which is undesirable since we want to identify isolated tokens to protect them while merging the others.\n\n### 3. Some claims didn’t seem substantiated enough\n\n- **Line 120, which is “PITOME remains robust to token partitioning strategies.”**\n\nWe apologize for the confusion the statement has caused. Indeed, this was a typo mistake. What we meant to convey is that \"PITOME remains robust compared to other token partitioning strategies.\" In addition, we want to highlight that PITOME offers a better trade-off between speed and accuracy compared to previous BSM-based algorithms (i.e, ToMe, Diffrate, etc), while still being able to preserve spectral properties of the token space, similar to loop-based algorithms (i.e k-mean, spectral clustering, graph coarsening, etc).\n\n- **In line 276, “We contend that this improvement stems from the merging of less significant tokens in PITOME potentially enhancing the robustness of the language mode”**:\n\nWe agree that the dataset may contain noise. However, this noisiness can be interpreted as either biased or diverse perspectives. A possible explanation for the performance improvement in our token merging method is that the model treats all objects in the image equally, regardless of their size and the number of tokens they have. Large objects have their tokens merged, while smaller objects' tokens are preserved. Therefore, the number of tokens representing an object is not much different. This approach allows the model to avoid bias caused by object size and focus on the objects themselves rather than being biased by larger objects with a greater number of tokens. Additionally, by paying equal attention to all scene objects, the model aims to capture diverse perspectives.\n\n### **4. The role of Table 2**\n\nIn Table 2, we aim to demonstrate the following points:\n\n- PITOME can be combined with various backbones (as mentioned by the reviewer). In particular, we test PITOME with 2 backbones in Table 2 (BLIP, BLIP2) and two additional backbones in Figure 3 (CLIP and ALBEF).\n- We show that PiToMe, when combined with various backbones still outperforms state-of-the-art architecture (CLIP, ALBEF, UNITER, VilT, etc...).\n- In addition to the image-text retrieval task, we evaluated PITOME on various other tasks using multiple backbones. For the image classification task, we tested our algorithm on six backbones with two different pre-training styles (DeiT and MAE). We used two backbones (LLaVA-7B and LLaVA-13B) for the visual question-answering task. We tested on two backbones (BERT and DistilBERT) in the text classification task. These experiments confirm the versatility of our algorithms.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "5fruGes5WJ", "reviewer": "Reviewer_ZkPm", "summary": "This paper introduces an energy-based approach to the token merging process, utilizing energy scores to avoid erroneous merges by distinguishing between informative or isolated tokens and redundant tokens. This method enhances the efficiency of heuristic merging approaches and preserves the spectral properties between the original and merged graph, thus accelerating token-based architectures such as ViT. Specifically, the technique employs cosine similarity with neighboring tokens to evaluate the energy score. Tokens with a high energy score are considered redundant and can be merged, indicating they belong to large clusters (e.g., background). Conversely, tokens with low energy scores are treated as foreground tokens. Furthermore, the authors also present theoretical findings demonstrating that the proposed method more effectively approximates the spectral distance between the initial token spaces and the merged token set compared to existing approaches. The method has shown competitive results across four tasks: image-text retrieval, visual question answering with LLMs, image classification, and text classification, underscoring its effectiveness and significance in the field.", "questions": "* There are some ambiguities that need to be clarified in the methodology section. The authors claim that $m$ is a fixed constant margin; \n   however, according to the context, $m$ seems to be the threshold of the margin, and $1-m$ is the margin. If I am wrong, the following \n   description is confusing:\n   In lines 162-163, \"$m = 0.9 − 0.9 × l_i/l$, ... indicating an increasing margin as tokens move to deeper layers.\" This sentence seems to be \n   the complete opposite of the conclusion. Also, does $\\alpha = 1.0$ mean that when token $j$ is outside the margins, $f_m(x)$ is a \n   negative constant? Furthermore, there are no related ablation studies or discussions of the impact of the $\\alpha $.\n* In most of the experiments, the ratio $r$ is 0.95, 0.975, 0.9, and 0.925. Only the image classification results include a ratio $r = 0.7$. \n   Existing approaches (e.g., ToMe) can achieve ratios of $r = 0.5 \\sim 0.6$. I am curious about the consistency of the proposed method at \n   higher merging ratios.\n* Some existing work, such as TRIPS and CrossGET, has also investigated token merging. The lack of thorough discussion or comparison \n   with previous work weakens PiToMe's claimed novelty. I suggest the authors more clearly present their merits and differences in the paper.", "limitations": "- The authors discuss some limitations in the last section.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "* This paper is well-written and clearly presents both the proposed solution and the experimental results.\n* In addition to thorough experiments demonstrating the effectiveness of the proposed method, the paper provides a theoretical derivation to explain why PiToMe outperforms another related approach (e.g., ToMe).", "weaknesses": "* Some formulas and inferences are ambiguous, leading to misunderstandings that undermine the correctness of the theoretical explanations.\n* The lack of results for higher merging ratios weakens the practicality of the proposed approach.\n* There is a lack of discussion on related works (e.g., CrossGET [1], TRIPS[2]).\n\n[1] CrossGET: Cross-Guided Ensemble of Tokens for Accelerating Vision-Language Transformers, ICML 2024\n\n[2] TRIPS: Efficient Vision-and-Language Pre-training with Text-Relevant Image Patch Selection, EMNLP 2022", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your helpful feedback. In what follows, we will address your concerns individually.\n### **1. The authors claim that is a fixed constant margin; however, according to the context, $m$ seems to be the threshold of the margin, and $1-m$  is the margin.**\n\nWe're sorry for the confusion. As we use the cosine similarity to compute the energy score,  the value of $x$ in Eq. 4 will be in the range $(-1,1)$. A value close to 1 indicates that the two vectors point in the same direction (identical tokens). Thus, since $m=0.9-0.9\\cdot l_i/l$ , we have that for the first layer, the margin will have a value of 0.9, and only neighbors that have a cosine similarity larger than 0.9 will be considered as neighbors. Tokens outside this margin will have the value $x$ replaced by a negative constant $\\alpha$. The margin becomes adaptively \"wider\" in deeper layers as $m$ decreases. \n\n### **2. Does mean that when the token is outside the margins, is a negative constant? Furthermore, there are no related ablation studies or discussions of the impact of the $\\alpha$**\n\nYes,  due to the strict page limits, we could not include the ablation regarding these parameters, the margin $m$, and the lower bound $\\alpha$ . Recall that we used $\\alpha(\\exp(x-m) - 1)$  to smoothen the  $f_m(\\cdot)$  function to consider neighbor tokens that are outside but are close to the margin $m$. The larger $\\alpha$, the more consideration for these neighbors, and $\\alpha=0$   means we completely ignore them. The table below shows experiment results on the image-text retrieval task using different values of $\\alpha$ and $m$.\n\n| $r$ | $\\alpha=1.0$  | $\\alpha=0.5$  | $\\alpha=0.0$  |\n| --- | --- | --- | --- |\n| 0.85 | 519.98 | 518.66 | 515.9 |\n| 0.875 | 545.9 | 544.22 | 542.54 |\n| 0.9 | 562.82 | 562.42 | 561.92 |\n| 0.925 | 571.88 | 571.1 | 570.62 |\n| 0.95 | 577.5 | 577.43 | 577.4 |\n| 0.975 | 580.24 | 579.82 | 579.76 |\n\n### **3. In most of the experiments, the ratio is 0.95, 0.975, 0.9, and 0.925. Question about the consistency of the proposed method at higher merging ratios.**\n\nThank you for your comment. We define the ratio $r$ differently from the ratio $r$ as mentioned in your question. We define the ratio $r$ as the number of tokens remaining in *each layer* after merging, not as the percentage of total remaining tokens after compression. Since PITOME is applied to all layers, $(1-r)$ percent of tokens will be merged after each layer. For example, let's consider a ViT model with 12 layers and a ratio $r=0.9$. This means that 10% of the tokens will be merged after each layer. The percentage of remaining tokens after compression is thus given by:\n\n$$\nr_{\\text{remain}} = \\frac{\\sum_{i=1}^{12} 0.9^i}{12} = 0.538.\n$$\n\n$r_{\\text{remain}}$ is the ratio $r$ mentioned in your question, which means reducing nearly half the number of tokens the model needs to process and leading to about two times the throughput. This percentage can further decrease for larger models with more layers. For instance, in the BLIP2 model with 48 layers, we can achieve $r_{\\text{remain}} = 0.362$   if $r = 0.9$ . For large language models like LLaVA, $r_{\\text{remain}}$  can be even lower (in our paper we tested with $r_{\\text{remain}}$ ranging from 0.732 down to 0.277).\n\n### **4.  PiToMe compared to TRIPS and CrossGET**\n\nFor better readability we added a table to compare these works:\n\n|  | TRIPs | CrossGET | PiToMe |\n| --- | --- | --- | --- |\n| Method | selective protect and merge image token based attention score from [CLS] token from text encoder | Introduced two components: (i) Complete-Graph Soft Matching (CGSM): to merge tokens with the highest similarity scores. (ii) Cross-Guided Matching and Ensemble: introduce learnable tokens to provide cross-modal importance scores, guiding the CGSM algorithm and enabling weighted average merging. |  Introduced energy scores to identify mergeable and isolated (informative) tokens. Tokens in large clusters will have high energy scores and be merged.  |\n| Strength | boost the  model accuracy at a lower computational cost than the unaccelerated baseline model | (i) Can be applied to both modality dependence and independent models. (ii) achieve better accuracy than the previous method (ToMe) in both w/wo training | (i)Share the shame strength with CrossGET (ii)Robust against imbalanced clusters |\n| Weakness | It is tailored for modality dependent models like ALBEF, and still need pertaining before inference | CSGM is very sensitive to the token space’s distribution and is suboptimal when facing token space with imbalanced clusters (Confirmed by the author in the appendix section)  | Applied to only the ViT encoder of the VL model without any cross-modal guidance |\n\nSince these papers do not provide their source code, it is difficult to reproduce their results. Also, we would like to explain more clearly the weakness of the CSGM algorithm used in CrossGET:\n\n- CSGM's implementation divides all tokens into two disjoint sets, $T_s$ , and $T_d$, allowing only one token from $T_s$ to merge with one token in $T_d$. This is suboptimal for imbalanced clusters, such as large clusters with many tokens (e.g., backgrounds) and small clusters (e.g., small objects), which are common in practice.\n- For example, let's assume we have four tokens where three are close to each other and one is isolated. CSGM would merge two of the three close tokens and then merge the remaining close token with the isolated one, causing significant information distortion. The correct behavior should be to merge the three close tokens and leave the isolated one untouched.\n- PiToMe, on the other hand, assigns high energy scores to tokens in large clusters, prioritizing their merging while protecting isolated tokens. In the example above, the three close tokens are identified as mergeable, while the isolated token remains protected. Moreover, PiToMe can also benefit from cross-modality guidance techniques as add-ons to enhance performance.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "9uEDWL9hdl", "reviewer": "Reviewer_4Z7M", "summary": "This paper proposes Protect Informative Tokens Merging (PIToMe), a token merging method that safeguards crucial information-bearing tokens prior to the merging step. PIToMe focuses on the token-splitting step before token merging. Specifically, PIToMe defines and calculates an energy score for tokens to be merged, and marks the highest scored tokens as suitable candidates for merging. Experiments show that PIToMe consistently outperforms previous token merging methods such as ToMe, DiffRate, ToFu, etc. Theoretical analysis reveals that PIToMe preserves the intrinsic spectral properties to the original token space.", "questions": "1. Also on the topic of compression rate. In ToMe, r can be randomly set to achieve any compression rates. Can I randomly set the r values for each layer in PIToMe?", "limitations": "See weaknesses & questions. I may change the rating after carefully checking the replies and reviews from other reviewers.", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "1. Being the first method to consider the graph relations of tokens during token merging, the design of PIToMe is novel. Thorough theoretical analysis demonstrates the design insights of PIToMe.\n2. Although some improvements are not significant enough, PIToMe successfully outperforms the previous token merging methods. Considering that many investigations towards token merging have been conducted by many works, I consider the improvements, albeit minor, as strengths.\n3. Visualizations demonstrate the design insights of PIToMe. From those demonstrations, I could see that PIToMe merges the correct tokens in the image.", "weaknesses": "1. ToMe is actually capable of conducting token merging at a very high compression rate (see Table 10 of ToMe paper, ViT-L and ViT-H can achieve about 2.5x speedup). Another recent work on arXiv [1] also demonstrate that this compression rate can even increase to >3x. However, in the experiments reported by PIToMe, the biggest speedup I could find is about 2x. I wonder whether PIToMe still works out for higher compression rates, since the metric vital for finding token clusters gradually defines more tokens as informative tokens (Eq. 4 in this PIToMe article). \n\n[1] PYRA: Parallel Yielding Re-Activation for Training-Inference Efficient Task Adaptation (arXiv 2403.09192)", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your feedback and high score, and for recognizing the main contribution of our work. We would now address your concerns regarding the compression rate of PiToMe.\n\n### 1. ToMe is actually capable of conducting token merging at a very high compression rate (see Table 10 of ToMe paper; ViT-L and ViT-H can achieve about 2.5x speedup). Another recent work on arXiv [1] also demonstrates that this compression rate can even increase to >3x. However, in the experiments reported by PIToMe, the biggest speedup I could find is about 2x.\n\n ****\n\nOur PITOME can indeed achieve up to a $3\\times$ speedup, as evidenced in Figures 5 and 6 (in the submission). In these experiments, we benchmarked PiToMe against various baselines using different ratios of $r$, where the compression rate ranged from approximately $70\\%$ down to $30\\%$. Generally, performance dropped by approximately $0\\%$ to $3\\%$, keeping more than $95\\%$ of the baseline model's performance. Remarkably, on text-classification tasks (figure 10  in the submission), PiToMe can even compress down to $20\\%$ of the number of tokens. This resulted in training and inference speeds approximately $5\\times$ faster while maintaining accuracy above $85\\%$ (about a $7\\%$ accuracy drop compared to baseline ). Please refer to figures 2, 3, and 4 in the global rebuttal,  where we conduct experiments on a wider range of ratio $r$.\n\nThank you for recommending arXiv [1], which was accepted by ECCV24 on July 01, 2024. Indeed, modulating token features during token merging can mitigate the performance drops under a low compression rate and achieve up to $\\times3$ speed. However, we do not recommend compression rates higher than $60\\%$  because compressing beyond this rate leads to significant performance degradation in many tasks. As shown in the arXiv [1] (PYRA) and ToMe, achieving a $3\\times$ faster inference speed typically results in a $4\\%$ to $7\\%$ drop in accuracy compared to the baseline in image classification tasks, which is undesirable.  Also, please note that factors other than the compression rate, such as hardware and batch size, can affect the model's speed. Therefore, we are unable to fully compare PyRA with PiToMe as the author hasn't published their code.\n\n###  2. I wonder whether PITOME still works out for higher compression rates since the metric vital for finding token clusters gradually defines more tokens as informative tokens (Eq. 4 in this PITOME article) \n ****\nFirst, we want to clarify that Equation 4 defines the token energy score. In our approach, informative tokens (low energy) are clustered into a preserved group, which will not be merged, and we only merge the less informative tokens (top 2k tokens with highest energy). Like other compression methods, PITOME can handle higher compression rates; however, there is a trade-off between performance and compression rate.\n\nIt is important to note that the compression process primarily merges less informative tokens while preserving the informative ones, which is true as long as a reasonable ratio $( r )$ is maintained. This is demonstrated in all the trade-off figures, where PiToMe can maintain model performance before a significant drop occurs if  $( r )$ is too low. In the final version, we will include more ablation studies on higher compression rates with various $( r^i )$ ratios for each layer  $( l^i )$, as suggested by the reviewer.\n\n###  3. Also, on the topic of compression rate. In ToMe, r can be randomly set to achieve any compression rates. Can I randomly set the r values for each layer in PIToMe? \n ****\n In PITOME, the compression rate can be flexibly controlled based on the ratio r, representing the fraction of remaining tokens.  Specifically, each layer $l^i$ is controlled by a ratio $r^i$, meaning that $1- r^i$ of the tokens will be merged. The overall percentage of remaining tokens after compression is given by:\n\n$$\nr_{\\text{remain}} = \\frac{\\sum_{i=1}^{N} r^i}{N}\n$$\n\nFor example, if we consider a ViT with 12 layers $(N = 12)$ and $r = 0.9$, the percentage of remaining tokens after compression is $r_{\\text{remain}} = 0.538$. Similarly, for a BLIP2 model with 48 layers, $r_{\\text{remain}} = 0.362$ with $r = 0.9$.\n\nThus, it is feasible to set the value $r^i$ for each layer randomly. However, it is important to consider the trade-off between performance and compression. As shown in our results, performance dramatically drops when $r < 0.85$ for all layers.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
First, we are grateful to the reviewers for their valuable comments and detailed feedback. We are pleased that the **reviewers recognize our energy-based token merging as a novel idea** (**Reviewer zfJf** and **Reviewer 4Z7M**) with a theoretical foundation explaining the underlying mechanism (**Reviewer zfJf** and **Reviewer ZkPm**). All reviewers also acknowledged our extensive experiments on image, text, and image-text retrieval, demonstrating that PITOME achieves higher accuracy while maintaining the expected number of FLOPs and memory usage **(Reviewer JRPM** and **Reviewer 4Z7M**). 

Then, we would like to summarize the main contributions of our work:

- We are introducing a new concept called the energy score, which can be applied to various applications such as LLM, 3D point clouds, video processing, or PDEs. This could open new research avenues for designing an optimal energy score that accurately represents specific underlying data distributions. Additionally, it could lead to new research directions in fields like chemistry and physics.
- We provide a robust and solid theoretical foundation for understanding and applying the energy score concept, offering valuable insights for further research and development.
- We demonstrated PITOME's versatility through extensive experiments in various scenarios, including image-text retrieval, image classification, text classification, and VQA using LLAVA-7B and 13B. Additionally, we compared our method with top compression models in each specific task, showcasing its broad applicability and effectiveness. PITOME's accuracy can also benefit from existing techniques to improve its performance further.
- Significant efficiency improvements can lead to substantial resource savings and open up new applications due to the widespread use of Transformers and the high computational resources required

The reviewers raised several concerns, which we addressed in the individual response. We summarize the highlights of our responses as follows:

- **Performance comparison with Tome:** We discuss the advantages of our approach over the baselines, including Tome, across various tasks with notable performance gains. Furthermore, we provide a detailed analysis of the speed and compression rate comparison between our PITOME and Tome.
- **Impact of variable $m$ and $\alpha$**: We include additional ablation studies on various values of $m$ and $\alpha$ to showcase the effectiveness and robustness of our proposed PITOME.
- **Compression rate:**  We clarify the merging ratio $r$ used in our paper and discuss in detail the trade-off between performance and compression rate. 

Finally, we have carefully addressed all the reviewers' comments and questions. We will revise and update our final version, using one additional page, based on all the reviewers' suggestions.

Meta-review: This paper proposes a new token merging method, i.e., PIToMe,  to enhance the efficiency of Vision Transformers (ViTs) by merging tokens in a way that preserves crucial information. Different from previous methods, PIToMe uses an energy score to prioritize and protect informative tokens while merging redundant ones. In this way, the computational and memory requirements are reduced by 40-60% with minimal impact on accuracy. Superior performance is achieved in multiple tasks such as image classification, image-text retrieval, and visual question answering, demonstrating its effectiveness and robustness compared to existing token merging techniques. Furthermore, it theoretically preserves the spectral properties of the original tokens, contributing to its efficiency and performance stability.

This paper received four reviews, with ratings of 1 accept, 2 weak accept, and 1 borderline accept. All reviewers are overall positive about this paper. They recognized the novelty and contributions of this paper, such as novel ideas,  extensive empirical validation, higher performance, and good presentation.

Meanwhile, the reviewers pointed out some suggestive comments that should be considered in preparing the final version, such as a relatively narrow problem, dense mathematical content (difficult for readers to quickly grasp the idea), ambiguous formulas and inferences, lack of results for higher merging ratios, and lack of discussion on related works. The authors provided meaningful responses to the reviewers' concerns and the reviewers are generally satisfied with the rebuttal. I recommend acceptance and strongly suggest the authors take the reviewers' suggestive and detailed comments and the authors' promised revisions into consideration in the final version.
Decision: Accept (poster)