Spectrum-Preserving Token Merging (PiToMe)

Each dot is a token (a feature vector, shown here in 2D). The scene has three dense clusters of redundant tokens plus a handful of isolated informative token pairs sitting on their own. Similarity is a Gaussian kernel of feature distance, sim_ij = exp(−‖x_i−x_j‖² / 2σ²) with zero diagonal (on real features the paper uses cosine similarity of L2-normalized keys). PiToMe's novelty is the energy score E_i = mean_j ELU(sim_ij − m): a token surrounded by many similar tokens scores high (redundant, safe to merge), an isolated token scores low (informative, protect). Each layer removes r = floor(N − N·ratio) tokens: sort by energy, mark the top 2r as mergeable and pass the rest through untouched, then do bipartite soft matching inside the mergeable set (sources = mergeable[::2] each merged into their most-similar destination = mergeable[1::2]) via a size-weighted average, so a merged token's circle grows with the patches it represents and attention FLOPs (∝ N²) fall. The right panel is the money shot: it builds the normalized Laplacian L = I − D^−1/2 A D^−1/2 and compares the leading eigenvalues of the original vs merged token graph. PiToMe merges only redundant tokens, so those eigenvalues barely move and the spectral distance stays near zero (the spectrum-preserving guarantee, Theorem 1); naive ToMe matches purely by raw similarity with no protection, so it merges the isolated informative tokens away and its spectral distance climbs. (This is a 2D didactic illustration of the exact energy-score + protect-then-merge + spectral-distance mechanism, run to about 50% token reduction, the paper's operating regime; at extreme compression even PiToMe must eventually touch the informative tokens. The published method applies PiToMe off-the-shelf to ViT, CLIP, BLIP, BERT and LLaVA, saving 40–60% FLOPs with under 1% accuracy drop. TrungTin Nguyen is a co-author.)