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

We deeply thank you for your helpful review and greatly appreciate your feedback. We are glad you found that our method is “intuitive and works well”, and that the paper was “well written and easy to follow”. We address each of your concerns below.

Concern 1a: Evaluation: Two simple baselines are not enough.

It is difficult to respond to this without direct citations of comparable pruning works or merging follow-ups. To our knowledge, the vast majority of pruning methods (e.g A-Vit [1], EVit [2], DynamicVit [3]) require training a learned token selection module. This prevents their application to out-of-the-box models while also preventing speedups during training as they require padding. Furthermore, these methods almost all only present results on images, preventing us from comparing them. On the other hand, Token Merging and random masking are two widely used methods that have been demonstrated to work well on videos, and present the fairest comparison to our work.

However, the most applicable baseline we did find was Semantic-Aware Temporal Accumulation (STA) [5] which is applicable to pre-trained models out-of-the-box, but performs poorly when used during training. We re-implemented STA, optimized it further to use Flash-Attention, and then compared it to RLT in Tables 1 and 3 of the global rebuttal PDF. We find that STA is slower and performs worse in all cases than RLT. We will gladly include this result in the main text.

Concern 1b: For other experiments, no baselines are provided.

We presume that this comment refers to Tables 3, 4 and 5 of the main text. Table 3 is an ablation, and thus does not make sense to compare to other baselines. Table 4 and 5 measures the reduction in tokens in different datasets and FPS configurations. However, Token Merging, random masking and STA all reduce a constant number of tokens controlled by a single hyperparameter. Comparing the reduction from RLT to these baselines in this context does not make sense. We will reword our analysis in the paper to make this easier to follow for readers.

Concern 1c: The token merging baseline lacks details.

As stated in the Token Merging paper [4], in videos merging is conducted across both spatial and temporal dimensions. We will clarify this further in the paper.

Concern 2: The proposed method is too simple and intuitive, i.e. merging patches with similar pixels.

If a method yields significant performance improvements and is novel, it is a valuable contribution, regardless of its simplicity. In particular, Reviewers B8qa and N711 note our method is “very well motivated” and has “commendable originality”, and you note RLT’s intuitiveness in the Strengths section of the review. All three reviewers agree RLT contributes significant speedups. Crucially, RLT does not merge patches progressively. It finds which patches to remove before running the model. This key component enables it to remove different numbers of tokens for each input while avoiding the overhead of padding, which hobbles methods like A-Vit or DynamicVit. This point is central to the paper, and we will be sure to rewrite parts of the paper to emphasize this point better. Given our method’s novelty, simplicity and significant performance improvements, we believe that it provides an elegant solution to a problem that will be easy for many researchers to adopt in practice.

Concern 3: Some experimental results are conflicting.

We understand your concerns about the results on the learned length-encoding. As we state in the global rebuttal, supported by results in the PDF attachment, we observe no real difference with the RLT when training, but do observe a noticeable difference when combining other techniques like random masking with RLT. As we expect practitioners to combine RLT with other methods for maximizing speed, we decided to include these results to better inform the community. We will be sure to clarify the role of the learned positional embedding further in the text.

Given that we have addressed the primary concerns raised in your review, we kindly request that you adjust your score.

[1] Rao, Y., Zhao, W., Liu, B., Lu, J., Zhou, J. and Hsieh, C.J., 2021. Dynamicvit: Efficient vision transformers with dynamic token sparsification. Advances in neural information processing systems, 34, pp.13937-13949.

[2] Liang, Y., Ge, C., Tong, Z., Song, Y., Wang, J. and Xie, P., 2022. Not all patches are what you need: Expediting vision transformers via token reorganizations. arXiv preprint arXiv:2202.07800.

[3] Yin, H., Vahdat, A., Alvarez, J.M., Mallya, A., Kautz, J. and Molchanov, P., 2022. A-vit: Adaptive tokens for efficient vision transformer. In Proceedings of the IEEE/CVF conference on computer vision and pattern recognition (pp. 10809-10818).

[4] Bolya, D., Fu, C.Y., Dai, X., Zhang, P., Feichtenhofer, C. and Hoffman, J., 2022. Token merging: Your vit but faster. International conference on learning representations.

[5] Ding, S., Zhao, P., Zhang, X., Qian, R., Xiong, H. and Tian, Q., 2023. Prune spatio-temporal tokens by semantic-aware temporal accumulation. In Proceedings of the IEEE/CVF International Conference on Computer Vision (pp. 16945-16956).

We deeply appreciate your kind comments towards our work, and thank you for your detailed review. We are glad you found our work to be exceptionally presented, and our work to be high quality. To answer your question, the inspiration for this work came from one of the authors’ habit of watching live podcasts on YouTube. These are often hours long but have a still camera and a static background. Videos with large amounts of stationary content are prime candidates for methods like RLT - their visual information can be drastically compressed with minimal loss.

Thank you for your exceptionally thorough, helpful and clear review of our paper. We are glad you found our work to be “very well motivated”, “novel” and found it to “work better than other methods like random masking”. We address each of your concerns individually below.

Concern 1: Learned embeddings seem to hurt performance on ViT-L.

We address this in the global rebuttal. In fact, RLT achieves about the same performance when trained with the learned embedding, and the learned embedding is especially helpful when combined with random masking.

Concern 2a: Did you ever test whether the thresholding would fail? There are cases where this could be a concern.

We found that a single threshold worked well for all experiments. We measured this by visually inspecting pruned patches (as in Figure 6) and measuring the performance as a function of threshold (Figure 3) However, as you note, this is an approximation for checking whether two patches are similar. We agree it could potentially affect performance for specific tasks where pixel-level details matter: for example, video generation or pose estimation. In this paper we focused on action recognition because it is the de facto task for measuring the quality of learned video representations, and our results demonstrate that RLT does not decrease the quality of these representations. As such, we believe our use of a single threshold justifies the potential tradeoff on certain downstream tasks.

Concern 2b: How sensitive is RLT to the norm used? How did this compare across datasets?

It doesn’t matter which norm is used - we found there was no appreciable difference in performance with L1 or L2. In our case, we took inspiration for using the L1 norm and a single dataset-agnostic threshold from the way video compressors [1] are implemented. Using and tuning for other types of norms could result in small differences, but L1 is simple, fast to compute, and widely used.

The threshold for whether the average intensities in a block of pixels has sufficiently changed should be agnostic of the data distribution. Though the threshold value itself matters, we find that the content of the dataset videos determine the reduction from RLT itself. We include results for different values of the threshold in Table 6 of the global rebuttal PDF, supporting that the change in performance for different values of the threshold is similar for Kinetics and Something-Something v2. On the other hand, datasets with almost no motion (e.g Breakfast) will result in many pruned tokens even for extremely small thresholds.

Concern 3: How much can RLT compress the sequence length of different datasets?

We provide this analysis in Table 5 of the PDF. To be clear, each example in a dataset is compressed to a different number of tokens based on its content. We find that the average compressed sequence length does vary across datasets depending on their content; as mentioned in the main text, the Breakfast and COIN datasets have minimal motion, and RLT is able to successfully prune many more tokens.

Concern 4: Should RLT be trained for the same number of tokens or the same number of samples?

For the fairest comparison, we trained on the same number of samples. Since RLT significantly reduces the number of tokens with the same number of samples, we find that training for the same number of total tokens leads to improved performance. We demonstrate this in Table 4 of the PDF, and will include these in the final version of the paper.

Concern 5: How well does the RLT work when training from scratch? How easy is it to fine-tune the length embedding?

This is an excellent question, and one we would have liked to investigate as well. However, pre-training video transformers requires large amounts of compute that was outside of our resources. Secondly, masked pre-training (which is how all the checkpoints we fine-tuned were pretrained) already involves removing a large proportion of tokens, and thus RLT would have minimal speedup during pre-training. However, our hypothesis is that pre-training with a learned embedding would be particularly helpful during pre-training, since we noticed that training with random masking benefitted from a learned embedding, supported by Table 2 of the PDF.

Concern 6: Tables 2 and 3 are not very clear.

Thank you for pointing this out. We apologize for the lack of clarity and will gladly clean these issues up in the updated version of the manuscript. We have included fixed versions of these tables in the results PDF.

Question 1: Use of the term “tokenization" is unclear.

Thank you for bringing this to our attention. We agree that the term “tokenization” is unclear, and perhaps “patchification” would be a better alternative. We will gladly update this throughout the text to better distinguish our method from VQ-VAE and other tokenizers, as you mention.

Question 2: How would RLT perform if the length of all tokens is 1, no matter the threshold?

We are not entirely sure we understand the question, but it appears that what you refer to here is RLT without the length encoding. This result is in Table 4 of the main text, and performs about the same at inference time, and slightly worse when combined with random masking. If we have misunderstood the question, please feel free to clarify further.

Given that we have addressed the primary concerns raised in your review, would you consider adjusting your score?

[1] Wiegand, T., Sullivan, G.J., Bjontegaard, G. and Luthra, A., 2003. Overview of the H. 264/AVC video coding standard. IEEE Transactions on circuits and systems for video technology, 13(7), pp.560-576.