Technical Summary: ST-SimDiff

Problem Statement

Multimodal Large Language Models (MLLMs) face significant computational and storage bottlenecks when processing long videos. The standard paradigm involves sampling a video into a sequence of frames and converting each frame into hundreds or thousands of visual tokens. As video duration and resolution increase, the token count grows explosively, leading to prohibitive computational costs due to the quadratic complexity ($O(N^2)$) of the self-attention mechanism.

Existing token compression methods generally fall into two categories:

1. Importance-based pruning: Removing tokens with low attention scores (e.g., FastV, FasterVLM).
2. Similarity-based merging/selection: Combining or selecting tokens based on high similarity within frames or between adjacent frames (e.g., FrameFusion, VisionZip).

The authors identify two critical limitations in current approaches:

• Lack of Joint Spatio-Temporal Modeling: Existing methods often treat spatial and temporal correlations in isolation, failing to capture complex dynamic events that rely on the interplay of both dimensions.
• Neglect of "Difference": Current methods focus heavily on informational commonalities (similarity and importance) to reduce redundancy. However, they often overlook crucial changes, turning points, and dynamic shifts. Since video narratives are often driven by these events, a model that only seeks similarity risks smoothing over sudden actions, leading to misinterpretation.

Methodology: ST-SimDiff

The paper proposes ST-SimDiff, a training-free framework that balances Spatiotemporal Similarity (for identifying redundancy) and Temporal Difference (for capturing key events). The method operates on a spatio-temporal graph constructed from visual tokens and employs a parallel dual-selection strategy.

1. Spatio-Temporal Graph Construction

The visual tokens $T = \{t_1, \dots, t_N\}$ are modeled as vertices in a graph $G=(V, E)$. The edge set $E$ is the union of:

• Spatial Edges ($E_S$): Connect tokens that are spatially adjacent within the same frame.
• Temporal Edges ($E_T$): Connect tokens at the same spatial position across adjacent frames.
  Edge weights are defined by the cosine similarity of the feature vectors of the connected tokens.

2. Dual Selection Strategy

The framework executes two parallel selection processes:

A. Similarity-Based Representative Token Selection (SRTS)

• Goal: Compress static and redundant content.
• Process:
  1. Threshold the graph to retain only edges with weights above a similarity threshold $\tau_{sim}$.
  2. Apply a community detection algorithm (specifically connected components in the implementation) to identify clusters of highly similar tokens.
  3. Within each community, calculate a centrality score for each token based on its average similarity to others in the cluster.
  4. Retain the top tokens with the highest centrality scores from each community to form the set $T_{rep}$.

B. Difference-Based Event Token Selection (DETS)

• Goal: Preserve tokens capturing key dynamic shifts and turning points.
• Process:
  1. Analyze the temporal edges ($E_T$) in the graph.
  2. Identify pairs of temporally adjacent tokens where the similarity drops sharply (i.e., the weight falls below a difference threshold $\tau_{diff}$).
  3. Mark the subsequent token in such a pair as a critical event token, forming the set $T_{trans}$.

3. Final Reduction

The final token subset is the union of representative and event tokens ($T_{candidate} = T_{rep} \cup T_{trans}$). If the size of this set exceeds the target budget (determined by the compression ratio $r$), a final pruning step removes tokens with the lowest attention scores (based on shallow LLM layers) to strictly meet the token count constraint.

Key Contributions

1. New Perspective: The authors propose that similarity and difference should be given equal importance in video token compression, arguing that similarity identifies redundancy while difference captures key moments.
2. Spatio-Temporal Graph Framework: A unified model for complex spatio-temporal relationships that enables simultaneous screening for representative tokens and pivotal event tokens.
3. Dual Selection Strategy: A novel mechanism that combines community detection for static compression with temporal difference analysis for dynamic preservation.
4. Training-Free Efficiency: The method requires no additional training and achieves significant computational savings while maintaining or improving performance.

Experimental Results

The method was evaluated on three long-form video understanding benchmarks: VideoMME, LongVideoBench, and EgoSchema, using LLaVA-Video-7B and NVILA-8B as base models.

• Performance: ST-SimDiff consistently outperformed state-of-the-art baselines (including FastV, PruMerge, FasterVLM, VisionZip, and FrameFusion) across all configurations. Notably, at a 50% token retention ratio, ST-SimDiff's performance on some benchmarks matched or exceeded the original uncompressed model (100% tokens).
• Ablation Studies:
  • Adding the similarity module (+Sim) improved performance over the baseline.
  • Joint spatio-temporal modeling was more effective than spatial or temporal modeling alone.
  • Adding the difference module (++Diff) provided a significant performance leap, particularly at high compression ratios (30%), confirming its role as a safety net for preserving narrative-critical events.
• Computational Efficiency:
  • Inference Time: ST-SimDiff reduced inference time by up to 30.2% for 128-frame videos compared to the baseline.
  • Memory Usage: Peak GPU memory usage was reduced by 31.7% for 128-frame videos, enabling the processing of longer videos on hardware with limited memory.
  • Complexity: The framework operates with linear complexity $O(Nd)$, significantly lower than the quadratic complexity of the self-attention mechanism.

Significance

The paper claims that ST-SimDiff addresses a critical blind spot in existing video understanding research: the tendency to prioritize similarity while neglecting the "difference" that drives video narratives. By constructing a spatio-temporal graph and employing a dual-selection strategy, the method achieves a robust balance between compressing redundant static information and preserving essential dynamic events. This approach offers a principled and adaptive solution for efficient video understanding, demonstrating that high-quality video comprehension can be maintained with a drastically reduced token budget.