菜单
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.
默认使用会先检查来源的 Prompt；你也可以切换为直接命令，或下载本地副本。
决定是否安装前，请先阅读 SKILL.md，以及 SkillsMP 当前展示的配套文件。
用 Codex 或 Claude 帮你安装 复制这段 Prompt，粘贴到 Codex、Claude 或其他助手里，让它检查 Skill 页面并帮你完成安装。
直接命令不会经过审查 Prompt；运行前请先检查来源。
npx skills add https://github.com/ADu2021/skillXiv --skill sttm-spatio-temporal-token-merging-video命令会保持在同一行。复制前请横向滚动并检查完整内容。
想先保存到本地？可下载 SkillsMP 当前能够提供的文件。
正在显示 SKILL.md
基于 SOC 职业分类
| 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. |
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.
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.
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
Identify similar tokens across consecutive frames and merge them, chaining tokens in graphs:
class UnionFind:
"""Union-Find data structure for efficient temporal merging."""
def __init__(self, n):
self.parent = list(range(n))
self.rank = [0] * n
def find(self, x):
if self.parent[x] != x:
self.parent[x] = self.find(self.parent[x])
return self.parent[x]
def union(self, x, y):
px, py = self.find(x), self.find(y)
if px == py:
return
if self.rank[px] < self.rank[py]:
px, py = py, px
self.parent[py] = px
if self.rank[px] == self.rank[py]:
self.rank[px] += 1
def merge_tokens_temporal(frame_tokens_list: List[torch.Tensor],
temporal_threshold: float = 0.85) -> Dict:
"""
Merge tokens across consecutive frames using union-find.
Returns mapping of frame-local tokens to merged representatives.
"""
num_frames = len(frame_tokens_list)
# Build spatial trees for each frame
trees = [build_spatial_quadtree(ft) for ft in frame_tokens_list]
frames_tokens = []
for tree in trees:
tokens, _ = extract_quadtree_tokens(tree)
frames_tokens.append(tokens)
# Union-Find for token grouping
total_tokens = sum(t.shape[0] for t in frames_tokens)
uf = UnionFind(total_tokens)
token_idx = 0
frame_token_map = {} # Map frame_id -> local_token_id -> global_id
for frame_id, tokens in enumerate(frames_tokens):
frame_token_map[frame_id] = list(range(token_idx, token_idx + tokens.shape[0]))
token_idx += tokens.shape[0]
# Temporal merging: compare adjacent frames
for frame_id in range(num_frames - 1):
tokens_curr = frames_tokens[frame_id]
tokens_next = frames_tokens[frame_id + 1]
# Compute similarity between all pairs
sim = F.cosine_similarity(
tokens_curr.unsqueeze(1), # [N_curr, 1, D]
tokens_next.unsqueeze(0), # [1, N_next, D]
dim=-1
) # [N_curr, N_next]
# Greedy matching: each token in frame_curr matches at most one in frame_next
for i in range(tokens_curr.shape[0]):
j = torch.argmax(sim[i]).item()
if sim[i, j] >= temporal_threshold:
global_i = frame_token_map[frame_id][i]
global_j = frame_token_map[frame_id + 1][j]
uf.union(global_i, global_j)
# Build merged token groups
merged_groups = {}
for i in range(total_tokens):
root = uf.find(i)
if root not in merged_groups:
merged_groups[root] = []
merged_groups[root].append(i)
return merged_groups, frame_token_map
def get_merged_tokens(frames_tokens: List[torch.Tensor],
merged_groups: Dict) -> torch.Tensor:
"""Compute final merged token representations."""
all_tokens = torch.cat(frames_tokens, dim=0)
merged_tokens = []
for root_idx in sorted(merged_groups.keys()):
indices = merged_groups[root_idx]
merged = all_tokens[indices].mean(dim=0)
merged_tokens.append(merged)
return torch.stack(merged_tokens) if merged_tokens else torch.tensor([])
Reorder merged tokens in a coherent pattern (Z-curve spatial + temporal precedence) and adjust positional embeddings:
def reorder_tokens_zorder(spatial_info: List[Tuple],
temporal_order: List[int]) -> List[int]:
"""
Reorder tokens in Z-order (Morton order) within temporal precedence.
Z-order preserves spatial locality for attention efficiency.
"""
def xy_to_z(x, y):
"""Convert 2D coordinates to Z-order curve index."""
z = 0
for i in range(16): # 16-bit precision
z |= ((int(x) >> i) & 1) << (2 * i)
z |= ((int(y) >> i) & 1) << (2 * i + 1)
return z
# Sort tokens by (temporal_frame, z_order)
sorted_indices = sorted(
range(len(spatial_info)),
key=lambda i: (temporal_order[i], xy_to_z(spatial_info[i][0],
spatial_info[i][1]))
)
return sorted_indices
def adjust_positional_embeddings(merged_token_count: int,
original_seq_length: int) -> torch.Tensor:
"""
Adjust positional embeddings for merged tokens.
Interpolate from original position space to compressed space.
"""
pos_orig = torch.arange(original_seq_length).float()
pos_merged = torch.linspace(0, original_seq_length - 1,
merged_token_count)
# Interpolate embeddings (example using linear interpolation)
pos_embeddings_merged = torch.nn.functional.interpolate(
pos_orig.unsqueeze(0).unsqueeze(0),
size=merged_token_count,
mode='linear',
align_corners=False
).squeeze()
return pos_embeddings_merged
Apply token merging early in the model pipeline (typically layer 3-4 for 7B models) to maximize speedup:
import torch.nn as nn
def apply_sttm_to_video_llm(model: nn.Module,
video_frames: torch.Tensor,
insertion_layer: int = 3) -> torch.Tensor:
"""
Apply STTM: merge video tokens before processing through LLM layers.
video_frames: [num_frames, H, W, D] tensor
"""
num_frames = video_frames.shape[0]
# Step 1: Spatial merging (quadtree per frame)
frame_tokens_list = []
spatial_info_list = []
for frame_id in range(num_frames):
frame = video_frames[frame_id] # [H, W, D]
tree = build_spatial_quadtree(frame)
tokens, spatial_info = extract_quadtree_tokens(tree)
frame_tokens_list.append(tokens)
spatial_info_list.append(spatial_info)
# Step 2: Temporal merging
merged_groups, frame_token_map = merge_tokens_temporal(frame_tokens_list)
merged_tokens = get_merged_tokens(frame_tokens_list, merged_groups)
# Step 3: Reorder tokens
temporal_order = []
for frame_id, local_tokens in enumerate(frame_token_map.values()):
temporal_order.extend([frame_id] * len(local_tokens))
reordered_indices = reorder_tokens_zorder(spatial_info_list[0],
temporal_order)
# Apply reordering
merged_tokens_reordered = merged_tokens[reordered_indices]
# Step 4: Adjust positional embeddings
original_length = sum(t.shape[0] for t in frame_tokens_list)
pos_embeddings = adjust_positional_embeddings(
merged_tokens_reordered.shape[0],
original_length
)
# Add positional embeddings
merged_tokens_with_pos = merged_tokens_reordered + pos_embeddings.unsqueeze(-1)
return merged_tokens_with_pos
# Example integration with LLM
def forward_with_sttm(model: nn.Module,
video_input: torch.Tensor,
text_input: torch.Tensor,
compression_ratio: float = 0.5,
insertion_layer: int = 3):
"""Forward pass with STTM token merging applied at insertion_layer."""
# Tokenize video
video_tokens = model.encode_video(video_input)
# Apply STTM
video_tokens_merged = apply_sttm_to_video_llm(
model, video_tokens, insertion_layer
)
# Tokenize text
text_tokens = model.encode_text(text_input)
# Concatenate
combined_tokens = torch.cat([video_tokens_merged, text_tokens], dim=0)
# Pass through LLM layers (with insertion_layer applying merging)
output = model.lm_head(combined_tokens)
return output
| Parameter | Recommended Value | Notes |
|---|---|---|
| Spatial Similarity Threshold | 0.9 | Higher = more aggressive merging |
| Temporal Similarity Threshold | 0.85 | Controls frame-to-frame merging |
| Quadtree Max Depth | 3 | Limits minimum merge region size |
| Token Reduction Ratio | 50% | 0.5× = 2× speedup with <0.5% accuracy drop |
| Insertion Layer | 3-4 (7B models) | Optimal balance of speedup vs quality |
| KV Cache Saving | Up to 2× | Enabled by query-agnostic design |
| Z-Order Bit Precision | 16 bits | Sufficient for spatial coherence |
| Positional Embedding | Linear interpolation | Smooth adaptation to merged length |
When to use STTM:
When NOT to use STTM:
Common pitfalls:
Li, C., Zhang, X., Wu, Y., & Tan, M. (2025). Multi-Granular Spatio-Temporal Token Merging for Training-Free Acceleration of Video LLMs. arXiv:2507.07990. https://arxiv.org/abs/2507.07990