This paper introduces ToMA (Token Merge with Attention), a training-free framework designed to speed up Transformer-based diffusion models (like SDXL and Flux) by merging redundant tokens. Unlike previous methods that struggle to translate theoretical FLOP reductions into real-world speedups, ToMA aligns its operations with modern GPU architectures to achieve significant practical latency gains.
TL;DR
ToMA accelerates diffusion models by replacing inefficient token-reduction operations (like sorting) with GPU-friendly, attention-like matrix multiplications. By reformulating token merging as a submodular optimization problem and exploiting spatial/temporal redundancy, it achieves ~24% faster generation on SDXL and Flux with negligible impact on image quality.
What Problem Does This Paper Address?
Modern high-fidelity diffusion models have shifted toward Transformer architectures (e.g., DiT, U-ViT). While powerful, Transformers suffer from quadratic complexity: doubling the number of image patches (tokens) quadruples the computational cost of self-attention.
Existing "plug-and-play" solutions like ToMeSD or ToFu attempt to merge similar tokens to reduce this load. However, they rely on operations like sorting, gathering, and scattered memory writes. On modern GPUs, these operations are "inefficient primitives" that create massive overhead. When paired with highly optimized kernels like FlashAttention, the overhead of these older merging methods often negates any speed gains—sometimes even making the model slower than the baseline. ToMA aims to bridge this gap between theoretical efficiency and practical wall-clock speed.
Methods
ToMA redesigns the token merging pipeline to be "GPU-aligned" through three main innovations:
- Submodular Destination Selection: Instead of heuristic matching, ToMA treats the selection of "destination" tokens (the ones others will merge into) as a Facility Location problem. This is a submodular optimization task that ensures the selected tokens are diverse and provide maximum "coverage" of the original image information.
- Attention-like (Un)merging: ToMA formulates the merge and unmerge steps as linear transformations.
- Merge: It uses Scaled Dot-Product Attention (SDPA) to calculate weights between destination tokens and source tokens. This allows the merge to be implemented as a dense matrix multiplication ($AX$), which GPUs are exceptionally good at.
- Unmerge: To restore the original resolution, it uses the transpose of the merge matrix ($A^T X'$). The authors show that because their selection process ensures diverse tokens and uses a low "temperature" for weights, the transpose acts as a highly efficient approximation of the mathematically ideal pseudo-inverse.
- Locality and Redundancy Exploitation:
- Latent Space Locality: ToMA performs merging within local "tiles" or "stripes" of the image. This reduces the search space for the optimization and matches the natural spatial coherence of images.
- Sequential Redundancy: Since latent states in diffusion change gradually, ToMA reuses the same merge patterns across multiple denoising steps and layers, drastically reducing the frequency of the most expensive computations.
Datasets
The authors evaluated ToMA using:
- Prompts: Drawn from the GEMRec dataset and ImageNet-1K class names.
- Models: SDXL-base (UNet-based) and Flux.1-dev (DiT-based).
- Metrics: CLIP-T (text-image alignment), DINO (perceptual consistency), and FID (distributional similarity).
Key Insights and Ideas
- Hardware-Awareness is Mandatory: A method that reduces FLOPs but uses non-contiguous memory access is a "theoretical" win but a "practical" loss. ToMA’s "free ride" comes from using the same optimized kernels (SDPA/GEMM) that the Transformers themselves use.
- The "Transpose" Approximation: One of the most elegant findings is that a simple matrix transpose is sufficient for "unmerging" tokens. This works because the submodular selection ensures that destination tokens represent largely disjoint subsets of the image, making the merge matrix nearly orthonormal.
- Visualizing Latent Coherence: By using k-means clustering on hidden states, the authors show that even early in the denoising process, the "tokens" already form a rough preview of the final image. This justifies why local tiling works just as well as global merging while being much faster.
Key Results
- Speedups: ToMA reduces generation latency by 24% on SDXL and 23% on Flux.1-dev (on an NVIDIA RTX6000).
- Quality Preservation: It maintains high fidelity, with a DINO score change of less than 0.07. Qualitative results show that even at 50% token reduction, the images are nearly indistinguishable from the baseline.
- Comparison: ToMA consistently outperformed ToMeSD and ToFu. In many tests, ToMeSD was actually slower than the baseline (+42% latency) due to its sorting overhead, while ToMA provided a consistent speedup.
- FLOP Reduction: At a 50% merge ratio, ToMA yields a 2.3x to 3.4x reduction in layer-wise FLOPs.
Limitations and Future Work
- Custom Kernels: While ToMA uses standard matrix operations, the authors note that further speedups could be achieved by writing custom "tiled attention" kernels to eliminate the minor overhead of reshaping and memory copying between tiles.
- DiT Complexity: Applying token merging to Diffusion Transformers (like Flux) is trickier than UNets. ToMA requires specific rules for Flux, such as skipping the first 10 blocks (where text and image features fuse) and handling RoPE (Rotary Positional Embeddings) carefully to avoid "breaking" the model.
- Hyperparameter Tuning: The optimal number of tiles (e.g., 64) and the merge ratio require some manual balancing between speed and fine-grained detail.
Summary updated