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

Authors: rohan  choudhury
guanglei  zhu
sihan  liu
koichiro  niinuma
kris m kitani
lászló a jeni
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-15 06:24:58

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\%. Our project page is at  rccchoudhury.github.io/projects/rlt.

Main paper: 
 introduction: 
 Vision transformers [11] have enjoyed enormous success in modeling images and videos due to their scaling properties and minimal inductive bias. Unfortunately, training these models on videos, which generally have orders of magnitude more tokens than images, is significantly more expensive. One contributing factor is that video transformers tokenize videos by splitting them into uniformly sized spatiotemporal patches [2, 3] , then embed them into a latent token space. As a result, the number of tokens depends only on the video's length and resolution. Researchers are thus forced to work with very short videos (<10s), as well as significantly downsample them to low frames-per-second (FPS) and low spatial resolution.One promising solution to this problem is to reduce the number of input tokens. Compared to language input, videos are significantly less dense in information; many works observe that videos consist mostly of redundant or uninformative tokens [15, 39, 43] . However, existing methods that aim to reduce input tokens to vision transformers have had limited adoption. Learned pruning methods [34, 52] reduce model complexity measured by GFLOPS, but either incur significant overhead during training, or require padding to handle changing numbers of tokens, negating any speed-up during training. Random masking [1, 27] , though fast, decreases accuracy and thus requires more training time to match performance. Moreover, although methods like random masking and Token Merging [5] do lead to wall-clock speedups, they are not content-aware: they only remove a fixed number of Figure 1 : Toy Example. Given a set of input frames, with each square representing a patch, standard tokenization always produces the same number of tokens. RLT compares temporally consecutive patches and removes redundant ones, storing a single token and the run-length instead. tokens per video, and will reduce the same number of tokens from a high-speed, high-action clip as from a still image repeated over time.We argue that content-awareness can help more effectively reduce the number of input tokens. As an example, imagine an hour-long video of a lecture. Most of the frames are exactly the same over time, displaying a single slide. Existing methods would produce the same number of tokens from this as from an hour of motion-heavy GoPro footage, even though the two videos have significantly different amounts of content. On the other hand, video compressors, such as H.264 and H.265 [46, 41] , are explicitly content-aware: rather than encoding frames independently, they encode pixel differences between consecutive frames, drastically reducing video size when there is no change.We propose Run-Length Tokenization (RLT), which combines a simpler version of this idea with classical run-length encoding to tokenize videos for transformers. Our insight is that we can efficiently identify 'runs' of input patches that are repeated over time, enabling us to reduce the number of tokens based on the video content. When tokenizing the video, we compare consecutive patches in time and group together patches with sufficiently small differences. We then remove the "repeated" patches, and treat the remaining tokens as having variable length. Similar to how the string aaaabb can be run-length encoded as a4b2, we can add length information to each of the tokens, which incurs no additional overhead while retaining some of the information lost from removing the redundant tokens. Despite its simplicity, RLT works remarkably well -with it, we can fine-tune a video transformer in 40% faster wall-clock time than baseline ViTs while matching performance.Our contributions are as follows: we (1) propose RLT, an alternative method to tokenize videos for vision transformers, (2) thoroughly compare its performance and compare RLT's speed to prior methods, finding significant improvements, (3) evaluate RLT's performance on high-FPS and longer videos, and (4) ablate design choices and qualitatively visualize RLT's output. We believe RLT can be a key step to significantly accelerate and further scale video understanding.Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?Answer: [Yes] Justification: Our claims in the abstract and introduction are concretely linked to results in our Results section, and aspirational goals are clearly denoted.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 be perceived well by the reviewers. • The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings. • It is fine to include aspirational goals as motivation as long as it is clear that these goals are not attained by the paper. 
related work: 
 Video Transformers. Vision Transformers [11] have been successfully adapted to video [2, 3, 13, 26, 38] but are generally trained and evaluated on short (<10s) video clips with relatively few frames. To efficiently handle videos, many works incorporate video-specific inductive biases in their architectures [29, 22, 56] , such as memory [49, 35] , compression cues [48] , or modified attention mechanisms [30, 53] . Other methods, especially in video generation, project the video to a smaller latent space [20] and then split it into patches. We instead use the standard ViT formulation but apply a different tokenization scheme, reducing the number of input tokens to improve speed while maintaining performance. Video Tokenization. Prior to vision transformers, video architectures were designed to take in a fixed size input [14, 40, 55] . However, transformers can handle arbitrary numbers of input tokens [44] , and training on variable-sized inputs is standard in language modeling [23] ; this has been used to train vision transformers with variable resolutions [4, 10] . However, video transformers still generally use the spatiotemporal patch tokenization scheme introduced in [2, 3] which is content-agnostic: the number of tokens depends only on the video's length and resolution. Some works attempt to reduce input size by compressing the video to a latent space, then tokenizing [12, 33, 6] , but the number of tokens still depends strictly on the input video dimensions. On the other hand, standard video compressors like HEVC [41] and AVC [46] are content-aware: they actively consider the differences between consecutive frames for more efficient compression. Our work applies this idea to video transformers by condensing static tokens and tracking their length.Faster ViTs with Fewer Tokens. Several works have attempted to remove uninformative tokens from vision transformers. One line of work identifies such tokens either through learned modules or attention scores [34, 52, 28, 21] , and prunes them at each layer. Although transformers can handle variable sized inputs, these methods require padding as token counts change unpredictably with each layer. Other works combine tokens instead of pruning them ( [5, 37, 31, 51] ). Most of these works require training a model for pruning or merging, with the exception of Token Merging [5] , which demonstrates strong results at inference time. Inspired by the success of masked pre-training ( [17, 45, 43, 15] ), another line of work uses random masking to speed up training. Although masking leads to worse performance after the same number of batches, the dramatic speedup enables training for more epochs in less time [1, 10, 27, 50] . In contrast, our method matches the performance of base models with the same amount of data with large speedups, and can be stacked with random masking for even more speed benefits. Closely related to our method are EVEREST [18] and STA [36] which both exploit temporal similarity to identify redundant tokens. However, like [5] both these works require setting a constant number of tokens to remove from each video, while RLT can remove varying numbers of tokens based on the video content.Question: Does the paper discuss the limitations of the work performed by the authors?Answer: [Yes]Justification: We include a limitations section at the end of the paper and discuss some of the weaknesses of our method that we hope future work can address.Guidelines:• The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper. • The authors are encouraged to create a 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 on 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 a few datasets or with a few runs. In general, empirical results often depend on implicit assumptions, which should be articulated. • The authors should reflect on the factors that influence the performance of the approach.For example, a facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or a speech-to-text system might not 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 to address problems of privacy and fairness. • 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 acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an important role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations. 
method: 
 Consider a vision transformer that takes as input a video V ∈ R C×T ×H×W . The standard tokenization scheme splits V into a set P of uniformly sized, non-overlapping patches, each with size C × D x × D y × D t , with P t called the tubelet size. These patches are projected to a lower dimension d embed with an MLP E, resulting in N P tokens, with each corresponding to a distinct spatiotemporal location. This results in the same number of tokens for any input video that has the same size.In contrast, our goal is to to identify input patches that are extremely similar, then compress these redundant patches, increasing throughput and training time. Our approach is illustrated in Figure 2 .In particular, we focus on temporally consecutive patches, those which have the same x, y location and differ by one timestep. These "static patches" correspond to visual content that does not change or move over time, and such tokens can be easily compressed.Token Similarity. Unlike prior works, we aim to reduce the number of total input tokens by comparing patches rather than tokens. By operating on patches, we do not need to run the patch embedding E or any layer of the model. As a result, we do not need to freeze parts of the model or propagate gradients through the pruning operation, which would require padding and negate potential speedups. This contrasts with prior works which progressively prune or combine tokens after each layer in the transformer. Furthermore, by identifying redundant patches, we can pre-compute the token distributions of various datasets and sizes of examples, allowing us to employ techniques like example-packing [23] . Finally, operating on visual patches is more interpretable and is similar to the heuristics used by video encoders [41, 46] .We next define a criterion for determining whether two consecutive patches are static. Consider two temporally consecutive patches P 1 , P 2 that correspond to spatial location (x, y) and temporal locations t 1 , t EQUATIONwith P t2+Dt-1 xy being the temporally last spatial crop of in P 2 and P t1 xy the first spatial crop of P 1 . This operation compares the "start" of the P 1 to the "end" of P 2 , with the idea being that if the first crop of token P 1 matches the last crop of token P 2 , the patches in between likely match as well. Notably, τ is a hyperparameter that needs to be tuned, but is dataset-agnostic; it simply encodes how much change between patches is allowed before they are considered different. τ controls the trade-off between speed and accuracy; while higher values reduce significantly more tokens, they treat tokens that are perceptibly different as being the same, reducing accuracy. We use τ > 0 since imperceptible artifacts can occur, and follow standard procedure by running ImageNet normalization before comparing patches. We typically use τ = 0.1, and provide experiments and visualizations on its effect in Section 4.3 and Appendix B.Pruning Procedure. To identify all static tokens, we run the prior comparison on all pairs of temporally consecutive patches in P obtaining their differences and only retaining those with difference less than τ . We always include the entirety of the first frame since there is no previous patch to compare it to. This results in a binary mask M static , which we can then apply withEQUATIONwith P ′ containing N P ′ tokens and P consisting of N P tokens. Note that N P ′ ≤ N P is always true; with RLT, we can never have more tokens than in the standard tokenization procedure, so the worst-case performance matches the standard vision transformer. RLT also incurs essentially no overhead as the entire process can be implemented entirely with parallelizable PyTorch [32] operations on the GPU, so training and inference are strictly faster.The simplicity of RLT is a major advantage: in contrast to other methods, we can take advantage of transformers' ability to handle variable input sizes, and do not need to provide any additional padding.Because we make no changes to the model itself, a video transformer using RLT can make use of hardware optimizations like Flash Attention [8, 9] and memory efficient kernels [25] .Notably, the pruning procedure is content-aware: some videos with large amounts of static content will result in significantly fewer input tokens than videos with significant amounts of camera or subject motion. This is a desired outcome, and we discuss how to handle training with dynamic input sizes in Section 3.3.Although we have reduced the number of input patches, we know that each patch represents a 'run' of static patches, with length 1 corresponding to no static content, and length T corresponding to input time dimension length. Without information about the length of the 'run' of static patches, the transformer may not be able to compensate for information removed during the pruning procedure.To address this, Bolya et al. [5] introduced Proportional Attention, which weights each token by the number of tokens in each group. On the other hand, we opt to let the model learn this information: we treat each token as having variable length that we can communicate through a new positional encoding. Specifically, we use a factorized encoding, described in Dehghani et al. [10] , with one encoding ϕ xyt containing positional information and the other ϕ L corresponding to the length. We use a learnable length bias ϕ L consisting of a single parameter of size (T, d embed ). For a given 'run' of repeated patches, we always retain the initial patch P xyt , and thus can compute the new length ℓ i as the distance from xyt to the nearest 1 entry in M static along the t-axis. Concretely, forEQUATIONThis operation can also be efficiently implemented on the GPU, adding no overhead. Then, the full positional encoding becomesEQUATION) with the ϕ L [ℓ i ] representing the indexing operator. We add the positional encoding ϕ(T i ) to each token after running the patch embedding network E. Unlike the pruning procedure, since we use a learnable length encoding ϕ L , we propagate gradients to the positional embedding, enabling the model to learn how to optimally encode variable length tokens during fine-tuning.Since RLT is content-aware, the number of tokens varies significantly per example. Although transformers can natively handle any input size [44] , prior methods like DynamicViT [34] or A-ViT [52] produce different numbers of tokens at each layer; this requires padding or attention masking to handle batched inference during training. In our case, only the input token count is variable, but the number of tokens stays constant throughout the network, closer to the setting of NaViT [10] . Furthermore, since we know the input size before running the network, we can employ example packing [23] , an idea from language modeling where multiple inputs with variable sizes are packed together, and tokens from individual examples attend only to each other.At training time, the input to the transformer consists of a batch of tokenized videos, V 1 , V 2 , ...V B , each with size T 1 , T 2 , ...T B . Rather than pass an input (B, max i T i , d embed ) to the network, we concatenate the video tensors to produceV ′ = V 1 ⊕ V 2 ⊕ V 3 ...V B , resulting in input size (1, B i=1 T i , d embed ).We then construct a block-diagonal attention mask so that tokens only attend to other tokens from the same video, which we add during the attention operation. Since every token in V ′ is attending only to tokens from the same example, this does not reduce throughput and is also compatible with existing hardware-efficient attention implementations. To compute the class prediction in action recognition, we split each example out and compute its prediction as the mean of each example token, as in [43] . We then project it to dimension N C , resulting in output of size (B, N C ) to which we can apply standard cross-entropy losses during training. We note that typically example packing results in a constant number of input tokens, with a variable number of input examples. A key difference between RLT and Dehghani et al. [10] is that data augmentations such as RandAugment [7] can alter the visual content and thus number of tokens of input videos, rendering greedy example packing strategies inapplicable during data loading. We opt to use a constant number of examples per GPU, with high enough batch size sufficiently reducing variance in input size.Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?Question: Does the paper provide open access to the data and code, with sufficient instructions to faithfully reproduce the main experimental results, as described in supplemental material?Answer: [Yes] Justification: We include the code in the submission which has all the necessary files to run the experiments from the paper. We have no dataset contribution and thus do not include any data.Guidelines:• The answer NA means that paper does not include experiments requiring code. • Providing as much information as possible in supplemental material (appended to the paper) is recommended, but including URLs to data and code is permitted. 
experimental results: 
 To analyze RLT's impact on performance and speed, we conduct several experiments on standard action recognition tasks. We measure the speedup on model training at several scales in Section 4.1 as well as RLT's effect as a drop-in addition at inference time in Section 4.2. We perform ablations in Section 4.3, then evaluate RLT's effect on higher FPS videos and long video datasets in Section 4.4. Finally, we provide qualitative visualizations in Section 4.5.In Table 1 we evaluate RLT's impact on the performance of video transformers during training and its resulting speedup. We fine-tune ViT-B and ViT-L from pre-trained VideoMAE [43, 45] comparing the speed and performance with standard tokenization, random masking, and RLT. We evaluate random masking by removing k tokens, with k being the mean number of tokens pruned by RLT on a given dataset. For the most fair speed comparison, all evaluated models are trained with mixed-precision, memory-efficient attention and Flash Attention where possible using an 8xH100 node, as well as the optimized data loader from AVION [54] to avoid data loading bottlenecks. We use the standard Vision Transformer rather than more complex architectures such as TimesFormer [3] or MViT [26] ; we found that it was significantly simpler and more efficient, matching observations from Ryali et al. [38] . We limit our analysis to fine-tuning due to computational constraints. We compare against the baseline vision transformer, as well as Token Merging and STA [36] . We also include a random masking baseline where the masking fraction is set to the average number of tokens removed by RLT, which is a stronger baseline than using a fixed standard fraction such as 0.5.Compared to standard tokenization, RLT achieves a speed-up of up to 40%, even with heavily optimized implementations. RLT achieves the best trade-off between performance and speed, with better performance than random masking while achieving the same speedup. This demonstrates that the choice of which tokens to remove makes a nontrivial difference, and that properly identifying redundant tokens is important.Compared to standard tokenization, RLT achieves a speed-up of up to 40%, even with heavily optimized implementations. RLT achieves the best trade-off between performance and speed, with better performance than random masking while achieving the same speedup. In particular, RLT is much faster to train than Token Merging since it is compatible with hardware-optimized implementations such as Flash-Attention [8, 9] . Unlike random masking, RLT matches the performance of the baseline ViT after the same number of training batches, while random masking requires significantly more epochs to catch up. RLT matches baseline performance across multiple scales, indicating that RLT does not degrade performance while considerably accelerating training.Although RLT was designed to speed up training, it can be used as a drop-in replacement for standard tokenization, similar to Token Merging [5] . In Table 2 we compare the top-1 accuracy, GFLOPs and throughput with RLT to standard tokenization and Token Merging [5] . We also compare against random masking for completeness, although it is intended only for training time [27] . For the most fair comparison, we randomly mask out P tokens for each example, where P is the mean number of tokens used by RLT; for Kinetics-400 and SSv2 this was P = 0.72. We do not compare to learned pruning methods like A-ViT [52] since those only present results on images. We measure throughput in clips-per-second, with each model running on a single clip at a time. In practice, video models are evaluated on multiple temporal and spatial crops; following VideoMAE [43] we measure GFLOPs on single clip and measure accuracy with 4 temporal and 3 spatial crops.Across model sizes, RLT consistently delivers the best tradeoff between speed and accuracy. The benefit becomes more pronounced as model size increases, as at larger parameter counts, the attention operation begins to dominate the computation. Compared to baselines, RLT is significantly faster than Token Merging and outperforms all other baselines on accuracy. Token Merging cannot make use of Flash Attention and other optimizations due to its reliance on a weighted attention operation, slowingSomething-Something-v2 it down in comparison to RLT. Although worse than RLT, random masking performs surprisingly well, likely due to the fact that most tokens in videos are redundant. Random masking can also be combined with RLT for further speed benefits, with smaller resulting performance gaps than in [27] . However, achieving the optimal performance-throughput tradeoff with random masking requires tuning for each dataset, while RLT is natively content-aware, achieving higher accuracy at similar speeds without tuning. Similarly, Token Merging [5] requires changing the r parameter based on the model size and is not content aware, limiting its speed-up in highly static videos.We ablate our design choices for RLT in Figure 3 and Difference Threshold. The only tunable hyperparameter in RLT is the threshold τ , which controls the sensitivity to change between temporally consecutive tokens. Lower values of τ indicate higher sensitivty to change. We vary tau and compare the final action recognition accuracy vs. throughput and wall-clock time for several configurations, both for training and inference. These results are shown in Figure 3 . We find that using τ = 0.1 offered the best tradeoff in speed and performance: it matches the baseline performance while delivering a 37% speedup in training. Lower values of τ lead to similar performance, but with less of a speedup, while high values deliver larger speedups at a cost to performance. We attribute this to the existence of a 'difference cut-off': at some point, the tokens are too different to be grouped together, and the resulting tokens do not obey the assumptions made by RLT. We also note that τ is dataset-agnostic: it simply describes how much pixel difference is needed to consider two 16x16 patches different, and the same value of τ leads to different reductions across datasets based on the video content.Length Encoding. We ablate the effect of our length encoding mechanism in Table 3 . When using RLT by itself, length encoding has minimal effect. However, when combining RLT with random masking, we note a clear improvement. Due RLT's structured and predictable pruning, length encoding may be unnecessary: the transformer is able to mostly understand the length of various tokens by their associated spatial positional encoding. However, once random masking is introduced, the structure is removed, and the length encoding adds crucial information. Since including the length encoding is strictly more information and has no negative effect, we default to including it.Standard action recognition datasets consist of short clips with downsampled FPS; an input example typically spans 2 seconds. One potential advantage of RLT is that by reducing the total number of tokens, training becomes more tractable for both longer videos and higher FPS. We evaluate the effect of training with RLT in Table 5 on action recognition datasets with higher FPS along with their training time. As before, we fine-tune these models from pre-trained VideoMAE checkpoints. Although these checkpoints were pre-trained at 7.5 FPS, we can still compare with the baseline performance to observe differences in training time or quality. Similar to the result from Table 1 , we find that ViTs trained with RLT can match performance but train significantly faster, with the speed-up increasing with the FPS.We next analyze the number of total tokens in RLT compared to the baseline for several video datasets in Table 4 , including datasets with longer videos as well as higher FPS. Matching the result from Table 5 , at higher FPS, RLT consistently reduces the tokens by a higher proportion. This matches our intuition, since tokens between two redundant tokens at lower FPS are likely to be similar and also be removed. Furthermore, on longer video datasets, RLT can reduce the number of tokens by significantly larger margins, with reductions of up to 80% on COIN and Breakfast. These datasets in particular consist of videos filmed with fixed cameras and largely static backgrounds, demonstrating RLT's potential to drastically speed up transformers on these types of videos. Although in practice, researchers do not typically train on raw videos with large number of frames due to the heavy cost of video decoding on academic clusters, RLT presents a promising way to efficiently train on these videos at scale.We provide some qualitative visualizations of the tokens RLT removes in Figure 4 . As desired, input patches that are repeated over time are pruned by RLT. This intuitively matches with how humans often pay less attention to static tokens over time. In the top example, most of the background is black, with some motion taking place in the foreground. RLT is able to remove the constant black portions, drastically reducing the number of tokens. Similarly in the second example, RLT ensures that the tokens containing motion, with the boy's hands and instrument, are not modified, but prunes the static background. In the lower two examples, the person using the drill and the girl in the foreground move around significantly, reducing the amount of tokens that can be compressed. In such cases where there is significant subject or camera motion, RLT removes fewer tokens, resulting in similar token counts to standard tokenization. However, the sensitivity of RLT to small perturbations and motion depends entirely on the τ hyperparameter. We provide further example visualizations and visualize the effect of different values of τ in Appendix B and on our project page. In Figure 5 we demonstrate the effect that the τ hyperparameter has on the input tokens. We see that as τ increases, more and more patches are included, and after τ = 0.1, some patches that have change in them are pruned incorrectly. On the other hand, τ = 0 includes many patches with essentially imperceptible change, which is also undesired. 
conclusion: 
 Summary We present Run-Length Tokenization (RLT), a simple alternative to standard video tokenization for video transformers that replaces temporally redundant tokens with a single token of variable length. RLT decreases transformer training and inference wall-clock time by up to 40%m achieves a better speed-accuracy tradeoff than prior works, and is simple to implement and combine with other methods. RLT demonstrates strong results during finetuning, especially at higher FPS, and even works well when applied to models without any training.Limitations Though RLT works well, it relies on a heuristic to compare temporally consecutive tokens, which could include extra tokens that are unused by the transformer. While RLT speeds up video transformers significantly, it cannot be used for dense vision tasks, such as point tracking or video generation, that require the same number of output tokens as input tokens; RLT reduces tokens before running the model and does not replace them. Furthermore, RLT does not handle camera motion well: in a video with constant camera motion, few tokens will be removed, leading to no speedup. Future work will be necessary to overcome these limitations, and we hope that RLT can inspire more research on efficient video transformers.Datasets. We train and evaluate RLT on Kinetics-400 (K400) [19] and Something-Something-v2 (SSv2) [16] . We also included experiments measuring the token reduction on the Breakfast [24] and COIN [42] datasets, both of which are smaller-scale datasets involving longer videos that range from 2-5 minutes. In particular, these datasets contain lots of fixed-camera videos with static backgrounds, leading to particularly high token reductions from RLT.Training Recipe. We do not change hyperparameters when finetuning models with different tokenization strategies, as we found the provided set to be optimal in our experiments. We follow the recommended training recipes from VideoMAE for each model size, namely training for up to 100 epochs, with batch size 256, learning rate with warm-up to 1 × 10 -3 for 5 epochs, then cosine annealing down to 1 × 10 -6 . We also use RandAugment, random erasing, CutMix, and standard cropping/scaling and flipping. We do not use MixUp since it can severely affect the efficacy of RLT, and we found that removing it and only using CutMix did not affect our experiments. We also used random erasing with a single value rather than noise, enabling some of the erased tokens to be removed by RLT.All experiments were conducted with 8xH100 Nvidia GPUs with 128 CPU cores, with 16 workers per GPU. The inference-time results were computed on a single GPU, along with the throughput and FLOPS analysis. One important detail is that data loading is often a bottleneck. We mainly relied on the fast video data loader from AVION [54] , but NVIDIA DALI also works very well. However, we only recomend to use DALI on A100 or newer chips, as earlier generations have an insufficient number of dedicated decoder hardware. Each training run for the paper is specified in hours, but this does not include a few months of work testing and debugging. We used a single node for all work on this paper. 
experimental setting/details: 
 Question: Does the paper specify all the training and test details (e.g., data splits, hyperparameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?Answer: [Yes] Justification: We include data splits, hyperparameters and rational for choosing them in the Implementation details section of the appendix. This is also provided with the code.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 a 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. 
experiment statistical significance: 
 Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?Answer: [NA] Justification: Our experiments are deterministic, and none of the experiments require statistical significance analysis; we ensure all experiments are random-seeded and reproducible.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, confidence 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 are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run 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). • It should be clear whether the error bar is the standard deviation or the standard error of the mean. Justification: The impact of our work is simply to speed up existing methods, in this case vision transformers. We do not see any clear way for this to be maliciously used or for this to directly negatively impact society and thus did not discuss this in the main text. Guidelines:• The answer NA means that there is no societal impact of the work performed.• If the authors answer NA or No, they should explain why their work has no societal impact or 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. • The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a 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 is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology. • If there are 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 to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML). 
safeguards: 
 Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?Answer: [No] Justification: Our experiments are relatively small-scale and based on existing pre-trained models, and thus requires no such safeguards.Guidelines:• The answer NA means that the paper poses no such risks.• Released models that have a 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 to 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 a best faith effort.12. Licenses 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: All pre-trained models were cited for their authors, along with the codebases used. We reference these in the main text, supplement and code.Guidelines:• The answer NA means that the paper does not use 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 a URL. • The name of the license (e.g., CC-BY 4.0) should be included for each asset.• For scraped data from a particular source (e.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, paperswithcode.com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of a 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. • If this information is not available online, the authors are encouraged to reach out to the asset's creators. 
new assets: 
 Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?Answer: [Yes]Justification: We provide details about our method in the main text and supplement, and the code contains documentation.Guidelines:• The answer NA means that the paper does not release new assets.• Researchers should communicate the details of the dataset/code/model 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. 
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 as details about compensation (if any)?Answer: [NA] Justification: We include no human subject research in our work.Guidelines:• The answer NA means that the paper does not involve crowdsourcing nor research with human subjects. • Including this information in the supplemental material is fine, but if the main contribution 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. 
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 an equivalent approval/review based on the requirements of your country or institution) were obtained?Answer: [NA]Justification: We have no user studies and thus did not need an IRB.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 we expect authors to adhere to 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. 
 
 Appendix: We include some additional visualizations here to qualitatively demonstrate which tokens RLT prunes, as well as to analyze the qualitative effect of varying the difference threshold τ . In each figure, the whitened patches represent those RLT identified as static, and that are not passed to the transformer.In Figure 6 , we visualize a diverse range of samples and note that RLT consistently prunes out patches that repeat across consecutive frames. One case where RLT fails to remove many tokens is the 4th example from the top, which is from a ski jumper using a GoPro; the constant camera motion means that RLT is unable to identify almost any repeated patches.We highly encourage readers to visit our project page for video visualizations that better convey the effect of RLT.Figure 6 : More examples. We visualize RLT's effect on videos ranging from TV shows, movies, action sequences on a GoPro, and sports. RLT consistently prunes out tokens that are repeated and static, and includes all patches that change between frames, retaining as much information as possible while cutting the number of tokens significantly.NeurIPS Paper Checklist 


Decision: This well-written paper introduces a novel method for reducing the computational burden of video analysis models. 

The proposed method omits patches/tubelets that do not change significantly between frames, and uses a run-length embedding to capture the information about how much data is omitted. The result is a model that only needs to process the tokens that are changing in a video, which can lead to significant speedups depending on the video content, with little or no loss in performance on human action recognition tasks. The computational savings is greatest when the input video is static, but significant savings can be had in typical videos where the important activity take up only a small part of the total time, or where the motion activity is localized to a small area of the frame.

The method reduces static tokens in training time dynamically. RLT takes into account spatial changes with respect to the temporal aspect. The RLT method inspired by popular video compression techniques such as HEVC and AVC which are content aware, making RLT also content aware as part of the input embedding of the video transformer.

The rebuttal, and subsequent discussion, resolved most of the concerns of the initial reviews. One reviewer expressed concern that the method was "too simple". But, as the authors responded, this is not a weakness. Many important advances in ML have been at heart apparently simple ideas (e.g. "dropout"). In this case the contribution may perhaps be simple, but it is not trivial, and is worth being made known to the ML community.

The other main critique made by the reviewers had to do with the apparent loss in performance when RLT is used. However, the authors point out that there was a typo and the actual performance drop is minimal. It should be kept in mind that the main benefit of the approach is the significant speedup attained when running video transformer models.

Reviews: review: paper_summary: paper_summary: The authors present a compression or optimization technique applicable to video transformers for both training and inference paradigms. Through empirical evaluation, the work showcases efficiency gains achieved for fine-tuning video transformer models and also showcases inference time efficiency without any training at all, with minimal quality degradation. The code has been made available for reproducibility.
strength_weakness: strength_weakness: No additional weaknesses apart from the limitations pointed out by the authors in Section 5.
questions: questions: Out of curiosity, how did the formulation of RLT come up?
limitations: limitations: NA
paper_summary: paper_summary: Current video models usually need to process every patch or tubelet of every frame, no matter if the video is very dynamic or contains patches that almost never change (e.g. static backgrounds). This submission proposes to simply omit tubelets that do not change significantly between frames, and optionally add a run-length embedding to them that signifies for how many frames that token does not change. The result is a model that only needs to process the tokens that are changing in a video, which can lead to significant speedups depending on the video content, at no loss in performance on human action recognition tasks.
strength_weakness: strength_weakness: - In Table 3 it is shown that for the larger ViT-L, adding run length embeddings significantly hurts performance. On the smaller ViT-B model it achieves the same performance, but the significant performance drop on the large model calls into question how the run length encoding influences train and test dynamics, and how well tuned these ablations are.
- How well does the approach work when training from scratch compared to fine-tuning existing checkpoints? How easy is it to fine-tune in the additional run-length embedding? Would we see a similar performance drop of ViT-L as in Table 3 when training from scratch?
- Table 2 is quite messy. "ViT-B" should be greyed out, the Xs in the greyed out rows are black, and the bolding is inconsistent (ViT-L acc on Kinetics is best, and only 4 values from the entire table are bolded).
- Table 3 is not very clear. Shouldn't the second rows for each model size be called "RLT minus length" since the default RLT setting uses run length embeddings, and the third row is just "RLT"? The description of "Rand" and "length" are not very clear. The gain from combining length and rand does not seem very significant compared to the base performance.
- Table 4: How much can RLT compress the sequence length of other datasets? It should be quite cheap to evaluate this. 
- It's also not clear how much influence the threshold value has on different datasets. It would be important to know if the optimal threshold value differs much between datasets, or if there is a safe range of values it can be set to.
- When training a model with RLT, should one train for the same number of tokens or same number of samples? It's not clear how much of a difference this makes between datasets.
- Is there a case where the proposed thresholding approach fails? How sensitive is it to the norm used? What if there are small but crucial differences that are below the threshold but important for the task at hand? The paper only evaluates on human action recognition tasks which could be blind to such differences.
- The method of calculating patch differences is to compute the 1-norm between the beginning and end of the two adjacent patches respectively. However there could potentially be some cases where rapid motion through a patch could conceivably be missed by this method. Did the authors test whether this was ever the case or explore alternative difference calculation methods?
questions: questions: - The term "tokenization" is loaded with a lot of meaning, and in the introduction it's easy to assume the method performs VQ-VAE or KL-VAE like tokenization, while the method operates on spatio-temporal patches, i.e. tubeletes, that are linearly projected. I suggest making it clearer what is considered a token.
- How well would RLT perform at inference time if the run-length for all tokens is forced to be just 1, no matter the threshold?
limitations: limitations: The authors adequately address potential limitations.
paper_summary: paper_summary: In this paper, the authors propose run-length tokenization, an efficient video patch merging strategy to speed up the video transformer
strength_weakness: strength_weakness: Please refer to Questions
questions: questions: ### Strength
1. The paper is well-written and easy to follow
2. The proposed RLT is intuitive and works well

### Weakness.
1. My main concern is the experiment part is far from solid. In Tables 1 and 2, there are only two simple baselines Token Merging and random masking. Pruning is a well-studied research topic and there are many methods, the Token Merging also has many following works. Two simple baselines are not convincing. For the rest experiments, no baseline is provided. The lack of correct baselines hinders the correct evaluation of the proposed method.
2. Following 1, the token merging baseline lacks details, is it conducted within each frame? or along the temporal dimension like RLT.
3. The proposed method is somewhat too simple and intuitive, ie, merging the patches with similar pixels. 
4. Some experiment results are conflicting and confusing. In Table 3, the length encoding seems nonhelpful or even harmful for the RLT, while it is claimed as a contribution of the proposed methods.
limitations: limitations: Please refer to Questions

Comments: title: Official Comment by Reviewer N711
comment: I thank the authors for their response. Most of my concerns and questions were addressed in the rebuttal, but it is still not very clear to me where the proposed thresholding approach fails. Still, I believe that the proposed method will be highly useful to the video understanding community, and I am raising my score accordingly.

Regarding my question on how RLT would perform if the run length of all tokens is set to 1: The model would be trained with RLT, but at inference time one would ignore the threshold and every tubelet is only used once, and the run length is set to 1 for all of them accordingly.
Thanks again for your detailed and constructive review. Since the discussion period is coming to a close, would it be possible to take a look at our rebuttal and let us know if you either have more questions or would adjust your score? We really appreciate your feedback, and hope we have answered your questions sufficiently.
Thanks for your response! Could you perhaps provide a litte bit more detail about your concern on Q3?

To clarify our point, we found that the run-length encoding __does not__ hurt performance when combined with removing the tokens and __improves__ performance when combined with random masking. Random masking is used commonly to speed up training, and is required for techniques such as masked pre-training. Given this result, we felt it was important to include in the paper. To us, it seems overly harsh to reject the paper based on this alone.

Would it be possible to raise your score to a 5? Again, we really appreciate your helpful feedback, and will gladly clarify the points in this discussion in the manuscript.
Thanks for the efforts. 

The rebuttal solved my concern about Q1 and Q2. As for Q3, I think I hardly agree with it. 

Based on the rebuttal, I would raise my score to 4.
thank you for your response.