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

Summary

In this paper, the authors propose run-length tokenization, an efficient video patch merging strategy to speed up the video transformer

Strengths

Please refer to Questions

Weaknesses

Please refer to 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.

Rating

4

Confidence

3

Soundness

3

Presentation

3

Contribution

3

Limitations

Please refer to Questions

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.

Strengths

- The method is very well motivated and aims to tackle an important problem, e.g. as the paper states, encoding a lecture with static background shouldn't require the same sequence length as a busy GoPro video. Dropping tubelets based on the temporal differences is better motivated than e.g. randomly dropping tokens irrespective of the video complexity. - The RLT formulation ensures that in the worst case where every tubelet changes in every frame, the inference time and performance is as large as a non-RLT baseline (assuming the changes are greater than the threshold). With this formulation, the sequence length is quite short for static videos, and the same for very busy videos. - The architectural modifications required are minimal, and only consist of implementing sequence packing and adding a learnable run-length embedding. This enables fine-tuning existing video models rather than having to train from scratch. - As far as I can tell, the run-length "positional" embedding is novel - On Kinetics-400 and Something-Something-v2, RLT can maintain performance while being significantly faster to train. Compared to a random approach that is content-unaware, RLT works better.

Weaknesses

- 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

- 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?

Rating

7

Confidence

4

Soundness

2

Presentation

2

Contribution

3

Limitations

The authors adequately address potential limitations.

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.

Strengths

The paper introduces run length tokenization (RLT) as a mechanism to reduce static tokens in training time dynamically. RLT takes into account spatial changes with respect to the temporal aspect and effectively condense static tokens adding run length information in the input embedding. RLT draws inspiration from widely used 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 originality of the work is commendable and the presentation quality of the work is exceptional. The efficiency gains achieved using this tokenization mechanism are state of the art, in both training and inference time with no performance degradation makes this work exceptionally useful to the extended community to train and deploy video transformer models more efficiently than previous literature in the field.

Weaknesses

No additional weaknesses apart from the limitations pointed out by the authors in Section 5.

Questions

Out of curiosity, how did the formulation of RLT come up?

Rating

8

Confidence

4

Soundness

4

Presentation

4

Contribution

4

Limitations

NA

Similar related work

Good work! I would like to mention that this work is related to TokenExpansion [1], which uses token similarity to select and merge tokens to achieve training acceleration for transformers. Maybe it should be discussed. [1] Huang, Wenxuan, et al. "A General and Efficient Training for Transformer via Token Expansion." Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition. 2024.