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

TL;DR

Run-Length Tokenization (RLT) is a content-aware token reduction scheme for video ViTs: before patch embedding, compare temporally consecutive patches at the pixel level, drop any patch that matches its predecessor under an L1 threshold τ, and add a learnable length encoding so the model knows how long each surviving token’s “run” was. The pruning is a parallelizable pre-network op with essentially zero overhead, requires no training, is compatible with Flash Attention, and yields 30–40% faster fine-tuning of ViT-B/L/H on Kinetics-400 and Something-Something-v2 while matching baseline accuracy. On longer/higher-FPS datasets the gains compound — up to 80% token reduction on COIN and Breakfast, and a 2.1× wall-clock training speedup at 30 FPS on K400.

Key claims

Comparing patches in pixel space (before patch embedding) rather than tokens after some transformer layers is what lets RLT avoid padding, freezing, or backprop through pruning — yielding strictly faster training, not just lower GFLOPS [§3.1].
A pair of temporally consecutive 16×16 patches is declared “static” iff the L1 distance between the last frame-crop of the earlier patch and the first frame-crop of the later patch is below τ; τ=0.1 (ImageNet-normalized) is the recommended setting and is dataset-agnostic [§3.1, §4.3].
Pruned tokens are replaced by a learnable length positional encoding factorized alongside the standard spatiotemporal encoding, communicating run-length to the transformer; ablating length encoding has negligible effect alone but matters when stacked with random masking [§3.2, Table 3].
Dynamic input sizes are handled by NaViT-style example packing with a block-diagonal attention mask, which keeps batched training compatible with Flash Attention and memory-efficient kernels [§3.3].
Fine-tuning ViT-B from a VideoMAE checkpoint on Kinetics-400 takes 10.2h vs. 14.4h baseline (1.4× speedup) at matched accuracy 80.1; ViT-L: 15.4h vs. 21.6h at 84.7 vs. 84.8 [Table 4.2].
At inference time RLT is a drop-in replacement for standard tokenization that beats Token Merging on both speed and accuracy: on ViT-L Kinetics-400, 52.6 clips/s vs ToMe’s 19.3 at 84.6% vs 84.3% [Table 2].
Token Merging is bottlenecked by its weighted attention, which is incompatible with Flash Attention; this is why RLT’s wall-clock advantage exceeds what the GFLOPS comparison would suggest [§4.2].
Random masking at the same average reduction fraction nearly matches RLT on speed but underperforms on accuracy when training from the same number of batches (e.g. ViT-L K400: 83.1 vs 84.7) — content-awareness has measurable value beyond raw token-count reduction [Table 4.2].
Token-reduction proportion grows with FPS and video length: -29% at 7.5 FPS K400, -45% at 30 FPS K400, -71% on COIN, -79% on Breakfast [Table 5].
At 30 FPS on K400, RLT cuts ViT-L training time from 110h to 52.3h (2.1× speedup) at matched accuracy, suggesting that the standard low-FPS short-clip evaluation regime systematically understates RLT’s value [Table 5].

Method

A standard video ViT splits an input video into a 3D grid of uniformly-sized spatiotemporal patches (tubelet size t, spatial size 16×16), each then projected by an MLP into a token. RLT inserts one parallelizable step before the patch-embedding MLP: for every pair of temporally adjacent patches at the same spatial location, take the L1 distance between the last frame-crop of the earlier patch and the first frame-crop of the later patch; if below threshold τ, mark the later patch as static and drop it. The first frame is always retained. The surviving tokens each get an extra factorized “length” positional encoding L[k] — a single learnable parameter per possible length k — that records how many input patches that token absorbed. Everything else in the transformer is untouched.

Because RLT never produces more tokens than standard tokenization, worst-case throughput equals the baseline. Because the pruning is a pre-network op realized as PyTorch tensor ops on the GPU, the overhead is negligible. Because the number of tokens stays constant through the network (unlike per-layer pruners like DynamicViT or A-ViT), no padding or attention masking is needed inside the transformer. Variable per-example token counts during training are handled by NaViT-style example packing with a block-diagonal mask, which keeps Flash Attention applicable. Fine-tuning is done from VideoMAE pretrained checkpoints; no architectural changes; only the input token sequence and the added length-encoding parameter L differ.

Results

Fine-tuning speed. ViT-B K400: 14.4h → 10.2h (1.4×) at 80.1% acc. ViT-L K400: 21.6h → 15.4h (1.4×) at 84.7 vs 84.8. ViT-L SSv2: 15.2h → 10.8h at 74.4 vs 74.3 [Table 4.2].
Inference throughput. ViT-L K400 throughput: 11.5 → 18.71 clips/s (1.62×) with 84.6% vs baseline 84.8%. ViT-H K400: 6.65 → 9.66 clips/s (1.45×) at 86.3 vs 86.8 [Table 2].
Vs. Token Merging. ViT-L K400 inference: RLT 18.71 clips/s at 84.6% vs ToMe 19.3 clips/s at 84.3% — comparable speed, higher accuracy; on ViT-B the gap widens because attention is a smaller fraction of compute, so ToMe’s weighted-attention overhead hurts more [Table 2].
Vs. random masking at matched reduction. Random ViT-L K400: 83.1; RLT: 84.7 at identical 15.4h wall-clock [Table 4.2]. The reduction is content-aware: lecture/static videos get pruned heavily, GoPro footage barely at all.
Scaling with FPS and length. ViT-L K400 at 30 FPS: 110h → 52.3h (2.1×) at 86.3 → 86.2; on Breakfast and COIN (longer videos, mostly-static cameras), 79% / 71% token reduction [Tables 5, 6].
Threshold robustness. τ ablation shows a wide sweet spot near τ=0.1; too-low τ keeps imperceptibly-different tokens, too-high τ merges actually different tokens. τ is dataset-agnostic — the same value is reused across K400, SSv2, EK-100, COIN, Breakfast [§4.3, Fig. 3].

Why it’s interesting

For any internal video model that ingests raw RGB frames — encoders for video understanding, perception backbones for VLAs, or even diffusion-side conditioning paths that take video context — RLT is a free pre-processing step that exploits exactly the redundancy that motivates H.264/H.265: most temporally-adjacent pixel patches are unchanged. The “free” qualifier is unusually clean here because the method (a) requires no training, (b) runs entirely on GPU as a tensor op, (c) is content-adaptive without per-dataset tuning, and (d) preserves Flash Attention. The scaling story is the more interesting one: gains compound with FPS and video length, which is precisely the regime Luma cares about for long-video understanding and long-context world models. The method does not directly apply to the generation side (where every token is being produced rather than encoded), but the underlying observation — that video temporal redundancy can be made architectural rather than learned — connects to the generation-side compression sub-problem studied in Context Length / Quality Trade-off in Video Generation (memory-encoder compression, KV-cache surprisal promotion). Worth contrasting: PFP/Context Forcing exploit redundancy learned by a compression encoder or surprisal heuristic; RLT exploits redundancy detected by a 1-line pixel-space comparison.