Don't Look Twice: Faster Video Transformers with Run-Length Tokenization

Rohan Choudhury, Guanglei Zhu, Sihan Liu, Kris M. Kitani, Laszlo Attila Jeni

Abstract

Video Vision Transformers (ViTs) face significant computational challenges due to the quadratic scaling of self-attention relative to the number of input tokens. Unlike static images, video sequences contain substantial temporal redundancy, where many spatial patches remain unchanged over multiple frames. We introduce Run-Length Tokenization (RLT), a simple yet effective content-aware method to compress video sequences by identifying and merging "runs" of identical patches. RLT replaces redundant temporal sequences with a single representative token and a learnable length encoding. Our results demonstrate that RLT can accelerate training by up to 40% and increase inference throughput by 35% with negligible accuracy loss. RLT is particularly effective for long-form and high-frame-rate videos, offering a hardware-efficient solution for modern video understanding.

1. Introduction

The transition from Image Vision Transformers to Video Vision Transformers has been marked by a massive increase in token counts. Standard video models typically decompose input clips into a grid of spatiotemporal "tubelets." While effective for capturing motion, this approach generates an order of magnitude more tokens than image-based models. A significant portion of these tokens are redundant, representing static backgrounds or slow-moving elements that do not change significantly between frames.

Current strategies to mitigate this computational burden generally fall into two categories: random masking and learned pruning. Random masking is computationally cheap but ignores video content, often requiring extended training to recover performance. Conversely, learned pruning or merging methods are content-aware but frequently introduce significant overhead or require complex, non-standard GPU operations to handle variable sequence lengths. We propose Run-Length Tokenization (RLT) as a middle ground: a method that is content-aware, computationally efficient, and hardware-friendly.

2. Run-Length Tokenization

RLT is inspired by the classic run-length encoding (RLE) algorithm used in data compression. The core idea is to treat the video as a sequence of spatial patches and compress consecutive identical patches along the temporal axis.

2.1 Static Patch Identification and Pruning

RLT operates as a pre-processing step before the video enters the transformer layers. For every spatial location $(x, y)$, the algorithm compares consecutive patches. If the $L1$ difference between the end of one patch and the start of the next falls below a predefined threshold $\tau$, the patches are considered part of a "run." RLT keeps only the first patch of the run and discards the subsequent redundant patches.

2.2 Run-Length Positional Encoding

To preserve temporal information after pruning, the model must understand how much "time" a single token represents. We introduce a learnable length bias ($\phi_L$) added to the standard positional embeddings. This encoding informs the transformer of the original duration of the compressed run, ensuring the model maintains a coherent sense of temporal progression.

2.3 Efficient Implementation via Example Packing

Because RLT is content-aware, different video clips result in different numbers of tokens. To maintain high GPU utilization and avoid inefficient padding, we employ "example packing"—a technique common in Large Language Model (LLM) training. Multiple compressed video sequences are packed into a single fixed-length sequence. A block-diagonal attention mask is then used to prevent tokens from different videos from attending to one another.

3. Experimental Evaluation

We evaluated RLT across a variety of benchmarks to test its versatility:

  • Action Recognition: Kinetics-400 (K400) for general action and Something-Something-v2 (SSv2) for fine-grained temporal interactions.
  • Long-form Video: COIN, Breakfast, and Epic-Kitchens-100 (EK-100), which feature high temporal redundancy.

Our findings indicate that RLT is highly adaptive. In high-action sequences, token reduction may be modest (e.g., 20%), whereas in static or long-form videos, RLT can reduce token counts by up to 80%.

4. Key Results and Insights

RLT demonstrates a superior Pareto frontier between accuracy and efficiency compared to standard ViT baselines and random masking techniques.

  • Speed and Throughput: RLT reduces wall-clock fine-tuning time for ViT-B and ViT-L architectures by 30-40%. During inference, throughput increases by 35% with a marginal accuracy impact of approximately 0.1%.
  • Scaling with Frame Rate: As video frame rates increase, the redundancy between frames grows. RLT capitalizes on this; when training at 30 FPS, RLT achieves a 2.1x speedup over standard training methods, which typically struggle with the resulting token explosion.
  • Architectural Simplicity: Because RLT functions at the patch level prior to the transformer backbone, it acts as a drop-in module. It does not require internal architectural modifications, making it compatible with various ViT variants.

5. Discussion and Limitations

While RLT provides significant gains in static or fixed-camera scenarios, its efficiency is sensitive to camera motion. In footage with constant panning, zooming, or handheld shaking, the $L1$ difference between patches often exceeds the threshold $\tau$, leading to fewer runs and diminished speedups.

Furthermore, RLT is currently optimized for classification tasks where the output is a single global label. For "dense" tasks such as video object segmentation or point tracking—which require a per-token output—the current pruning mechanism is not directly applicable. Future research will explore "re-inflation" techniques to map compressed tokens back to their original spatiotemporal coordinates for generative and dense prediction tasks.

Summary updated

Abstract

Video transformers are slow to train due to extremely large numbers of input tokens, even though many video tokens are repeated over time. Existing methods to remove uninformative tokens either have significant overhead, negating any speedup, or require tuning for different datasets and examples. We present Run-Length Tokenization (RLT), a simple approach to speed up video transformers inspired by run-length encoding for data compression. RLT efficiently finds and removes `runs' of patches that are repeated over time before model inference, then replaces them with a single patch and a positional encoding to represent the resulting token's new length. Our method is content-aware, requiring no tuning for different datasets, and fast, incurring negligible overhead. RLT yields a large speedup in training, reducing the wall-clock time to fine-tune a video transformer by 30% while matching baseline model performance. RLT also works without training, increasing model throughput by 35% with only 0.1% drop in accuracy. RLT speeds up training at 30 FPS by more than 100%, and on longer video datasets, can reduce the token count by up to 80%.
BibTeX
@inproceedings{choudhury2024don,
  author = {Rohan Choudhury and Guanglei Zhu and Sihan Liu and Kris M. Kitani and Laszlo Attila Jeni},
  title = {{Don't Look Twice: Faster Video Transformers with Run-Length Tokenization}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2024},
  url = {https://openreview.net/forum?id=b1ggjW00NI},
}
Figure