sttm-spatio-temporal-token-merging-video

name	sttm-spatio-temporal-token-merging-video
title	Multi-Granular Spatio-Temporal Token Merging for Training-Free Acceleration of Video LLMs
version	0.0.2
engine	skillxiv-v0.0.2-claude-opus-4.6
license	MIT
url	https://arxiv.org/abs/2507.07990
keywords	["Video LLM","Token Reduction","Spatio-Temporal Merging","Training-Free Acceleration","KV Cache Efficiency"]
description	Accelerate video LLMs by 2× with minimal accuracy loss using training-free spatio-temporal token merging that exploits video redundancy through quadtree-based spatial compression and temporal frame similarity, enabling efficient multi-turn reasoning with KV cache reuse.

STTM: Training-Free Acceleration of Video LLMs via Token Merging

Video LLMs process thousands of tokens per frame (video + text), causing quadratic KV cache memory growth and slow inference. STTM addresses this through principled token reduction that exploits video structure: spatial redundancy within frames and temporal redundancy across frames. Unlike query-aware methods that cannot reuse cached computations across questions, STTM is query-agnostic, enabling efficient KV cache reuse in multi-turn conversations.

The method uses quadtree-based hierarchical search for spatial merging (preserving fine details where needed) and union-find for efficient temporal merging. At 50% token reduction, accuracy drops only 0.5% while achieving 2× speedup.

Core Concept

Video is inherently redundant: regions of uniform color or texture don't need individual tokens, and consecutive frames have high similarity. STTM exploits both by (1) merging spatially uniform tokens within each frame via quadtree decomposition, and (2) merging temporally similar tokens across frames. Critically, this is done without query information, so the same compressed representation works for any downstream question.

The method operates early in the LLM pipeline (typically layer 3 for 7B models), replacing expensive token representations with merged tokens before costly attention operations.

Architecture Overview

• Quadtree Spatial Merging: Hierarchical frame decomposition with adaptive granularity
• Temporal Merging: Identifies similar tokens across consecutive frames, chains them in graphs
• Token Reordering: Z-shaped spatial ordering with temporal precedence for coherent linearization
• Positional Embedding Adjustment: Handles merged tokens in the positional encoding space
• Insertion Point: Early LLM layers (typically layer 3) before expensive multi-head attention
• KV Cache Reuse: Same merged tokens work across multiple questions without regeneration

Implementation

Step 1: Build Quadtree for Spatial Token Merging

Construct a quadtree for each frame where nodes represent token groups at different spatial granularities:

import torch
import torch.nn.functional as F
from typing import List, Dict, Tuple

class QuadTreeNode:
     ():
        .x_min, .y_min = x_min, y_min
        .x_max, .y_max = x_max, y_max
        .tokens = tokens  
        .depth = depth
        .children = []

     () -> torch.Tensor:
        
         .tokens.mean(dim=, keepdim=)

 () -> QuadTreeNode:
    
    h, w, d = frame_tokens.shape

     ():
        
        region = frame_tokens[y_min:y_max, x_min:x_max]
        region_flat = region.reshape(-, d)

        
         region_flat.shape[] <= :  
             QuadTreeNode(x_min, y_min, x_max, y_max,
                               region_flat.unsqueeze(), depth)

        
        sim = F.cosine_similarity(
            region_flat.unsqueeze(),  
            region_flat.unsqueeze(),  
            dim=-
        )  

        
        mean_sim = sim.mean().item()
         mean_sim >= similarity_threshold  depth >= :  
            merged = region_flat
             QuadTreeNode(x_min, y_min, x_max, y_max, merged, depth)

        
        mid_x = (x_min + x_max) // 
        mid_y = (y_min + y_max) // 

        node = QuadTreeNode(x_min, y_min, x_max, y_max, region_flat, depth)

        
        node.children.append(recursive_build(x_min, y_min, mid_x, mid_y, depth + ))
        node.children.append(recursive_build(mid_x, y_min, x_max, mid_y, depth + ))
        node.children.append(recursive_build(x_min, mid_y, mid_x, y_max, depth + ))
        node.children.append(recursive_build(mid_x, mid_y, x_max, y_max, depth + ))

         node

    root = recursive_build(, , w, h)
     root

 () -> [torch.Tensor, []]:
    
    tokens = []
    spatial_info = []  

     ():
          node.children:  
            merged = node.get_merged_token()
            tokens.append(merged)
            cx = (node.x_min + node.x_max) / 
            cy = (node.y_min + node.y_max) / 
            size = (node.x_max - node.x_min + node.y_max - node.y_min) / 
            spatial_info.append((cx, cy, size))
        :
             child  node.children:
                traverse(child)

    traverse(root)
     torch.cat(tokens, dim=), spatial_info