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