💻 computer science

Video Patch Pruning: Efficient Video Instance Segmentation via Early Token Reduction

This paper introduces Video Patch Pruning (VPP), a novel framework that leverages temporal prior knowledge and a differentiable mapping module to enable efficient early-layer token reduction in Vision Transformers, achieving up to 60% patch sparsity with minimal performance loss on video instance segmentation tasks.

Original authors: Patrick Glandorf, Thomas Norrenbrock, Bodo Rosenhahn

Published 2026-04-02

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: Patrick Glandorf, Thomas Norrenbrock, Bodo Rosenhahn

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

The Big Problem: The Overworked Chef

Imagine a high-end restaurant kitchen (the computer) trying to cook a complex dish (Video Instance Segmentation). The chef (the AI model) is a Vision Transformer (ViT).

In a traditional setup, the chef looks at every single ingredient on the counter, no matter how small or irrelevant. If you are filming a video of a person skateboarding, the chef looks at the skateboard, the person, the sky, the trees, the pavement, and every single leaf blowing in the wind.

This is incredibly accurate, but it's also exhausting and slow. The chef spends 90% of their energy analyzing the background (the trees and sky) just to find the skateboarder. This makes it impossible to serve the dish quickly on a small, portable stove (like a smartphone or a self-driving car's computer).

The Old Solution: Cutting the Fat Too Late

Previous attempts to speed this up were like a chef who cooks the whole meal first, tastes it, and then tries to throw away the boring parts.

The Issue: By the time the chef gets to the end of the cooking process, the "boring" parts have already been chopped, mixed, and heated. You can't easily remove them without ruining the dish.
The Result: These methods could only cut about 30% of the work. They still had to do most of the heavy lifting at the beginning.

The New Solution: Video Patch Pruning (VPP)

The authors of this paper introduced a new strategy called Video Patch Pruning (VPP). Think of this as a smart sous-chef who stands at the very front of the kitchen line.

Here is how it works, broken down into three simple concepts:

1. The "Memory" Trick (Temporal Prior Knowledge)

The smart sous-chef doesn't just look at the current frame (the current second of video). They remember what happened in the previous second.

Analogy: Imagine you are watching a movie. If a character is walking across the screen in frame 1, you know exactly where they will be in frame 2. You don't need to scan the whole screen to find them; you just look where they were a moment ago.
How it helps: The VPP system looks at the "high-level" features from the previous frame (where the important stuff was) and projects that knowledge onto the current frame. It tells the chef: "Ignore the sky and the trees right now; the skateboarder is definitely over here."

2. The "Early Cut" (Early Token Reduction)

Because the sous-chef knows where the action is before the cooking really begins, they can throw away the boring ingredients immediately.

The Magic: Instead of waiting until the end to cut the fat, VPP cuts the boring background patches right after the very first step of processing.
The Result: The chef only has to cook the "meat" (the foreground objects). This allows them to throw away up to 60% of the work, compared to the old 30% limit.

3. The "Safety Net" (Gumbel Noise)

You might ask: "What if a new skateboarder jumps into the frame from the side? Won't the chef miss them because they were only looking at the old spot?"

The Fix: The system uses a little bit of controlled randomness (called Gumbel noise). It's like the sous-chef saying, "I'm 95% sure the skateboarder is here, but I'll keep a tiny, tiny eye on the rest of the kitchen just in case something new appears."
This ensures that if a new object enters the scene, the system catches it immediately without needing to re-scan the whole room.

Why This Matters

The paper proves that this method is a game-changer for two main reasons:

Speed: It runs much faster. On a standard computer, it processes video frames significantly quicker than the old methods, making it possible to run on real-world devices like drones or cars.
Accuracy: Surprisingly, by throwing away so much "junk" data, the system actually gets better at finding objects. Because it isn't distracted by the background, it focuses its energy entirely on the important stuff.

The Bottom Line

Think of Video Patch Pruning as upgrading from a security guard who checks every single person in a stadium (slow and tiring) to a guard who uses a predictive algorithm. The new guard knows exactly where the VIPs are sitting based on where they were last time, so they only check those specific seats. They ignore the empty seats and the concession stands, saving massive amounts of time and energy while still catching the VIPs perfectly.

This allows AI to "see" video clearly and quickly, even on small, battery-powered devices.

1. Problem Statement

Video Instance Segmentation (VIS) requires the simultaneous detection, segmentation, and tracking of objects across video frames. While Vision Transformers (ViTs) have achieved state-of-the-art performance in this domain, their quadratic computational complexity with respect to the number of patches makes them too resource-intensive for edge devices.

Existing Patch Pruning methods (e.g., DynamicViT, SViT) attempt to mitigate this by removing less informative patches. However, they suffer from a critical limitation:

Late-Stage Reduction Only: Current methods enforce sparsity only in deeper layers (e.g., layers 3, 6, 9) while keeping early layers dense.
Lack of Early Selectivity: The authors demonstrate that early ViT layers lack Foreground Selectivity (FGS). They cannot reliably distinguish between foreground objects and background noise. Consequently, applying pruning to early layers based solely on current frame features results in random mask generation, leading to the loss of critical object information.
Image-Centric Limitation: Most methods treat frames as independent entities, ignoring temporal context which is crucial for video tasks.

2. Methodology: Video Patch Pruning (VPP)

The authors propose VPP, a novel framework that enables efficient patch reduction starting from the very first layer of the network by leveraging temporal prior knowledge.

A. Core Insight: Foreground Selectivity (FGS)

Through an ablation study, the authors found that FGS (the ability to identify object patches) increases linearly with network depth. Early layers (0–3) have low FGS (~60%), making them unsuitable for pruning without external guidance. Deeper layers (6+) achieve high FGS (>90%).

B. The Mapping-Selective Module (Map-SM)

To overcome the low FGS in early layers, VPP introduces a fully differentiable module called Map-SM that operates after the first layer.

Temporal Mapping: Instead of analyzing the current frame in isolation, Map-SM maps high-level, foreground-selective features from the previous frame ( $t-1$ ) onto the current frame ( $t$ ).
Association Matrix: It calculates a similarity score between current patches and retained patches from the previous frame to build an association matrix $A$ .
Gumbel-Softmax: To ensure differentiability and allow for exploration during training, the module uses Gumbel-Softmax noise. This allows the model to:
1. Compensate for Motion: Accurately track moving objects across frames.
2. Sparse Background Activation: Intentionally keep a sparse set of background patches active (via noise) to ensure new object instances entering the frame are not missed.
Mask Generation: The mapped features guide the selection of the top- $k$ patches to retain, effectively filtering out background noise immediately after the first layer.

C. Multi-Stage Pruning

VPP employs a hybrid pruning strategy:

Early Stage (Layer 1): Uses Map-SM to prune ~40% of patches by leveraging temporal context.
Deep Stages (Layers 3, 6, 9): Uses a standard Selective Module (SM) (similar to existing methods) to further reduce features based on current frame confidence.
Dynamic Mask Scaling: Unlike methods with fixed sparsity, VPP dynamically adjusts the mask size based on object instance size, allocating more resources to small objects and fewer to large ones.

3. Key Contributions

Early Token Reduction: VPP is the first method to successfully enable patch pruning in the early layers of ViTs for video tasks, achieving up to 60% total patch reduction (compared to the typical 30% limit of image-based methods).
Foreground Selectivity Analysis: The paper provides empirical evidence that early layers lack foreground selectivity, explaining why image-based pruning fails at early stages, and proposes a temporal solution.
Mapping-Selective Module: A lightweight, differentiable module that propagates spatio-temporal motion information to guide early pruning decisions without relying on classification tokens (making it suitable for dense prediction tasks).
State-of-the-Art Efficiency: VPP achieves superior performance with significantly lower computational costs compared to dense models and existing pruning baselines.

4. Experimental Results

The method was evaluated on Youtube-VIS 2019 and 2021 datasets using ViT-Adapter backbones (Tiny and Small).

Performance vs. Sparsity:
- At 55% Patch Keep Ratio (PKR), VPP (Small model) achieved 49.8 AP, dropping only 0.6% compared to the dense baseline (50.4 AP).
- In contrast, existing methods like SViT dropped 3.5% AP at similar sparsity levels.
- At 40% PKR, VPP maintained 48.5 AP (only -1.9% drop), whereas SViT dropped significantly more (-5.5%).
Foreground Retention (IoI):
- VPP achieved an Intersection over Instance (IoI) of 82.3% at 55% PKR, significantly outperforming SViT (73.7%). This proves VPP retains more critical foreground patches.
- VPP showed particular strength in retaining small objects (IoI of 87.3% for small instances).
Computational Efficiency:
- FLOPs: Reduced from 88.0 G to 59.9 G.
- Throughput: Achieved 25.94 FPS (backbone) and 8.13 FPS (full model), a significant speedup over the dense baseline (17.14 FPS / 6.58 FPS).
Robustness: In dynamic scene switches, VPP was able to reallocate the foreground mask and recover full object tracking within one timestep ( $t=2$ ), demonstrating rapid adaptation to new scenes.

5. Significance

This work fundamentally shifts the paradigm of ViT efficiency in video processing. By proving that temporal context can be used to guide early-stage pruning, VPP breaks the efficiency ceiling of current image-based methods. It enables the deployment of high-performance Video Instance Segmentation models on resource-constrained edge devices without sacrificing the accuracy required for safety-critical applications like autonomous driving. The approach demonstrates that "less is more" even at the very beginning of the network, provided the pruning is guided by the right temporal priors.