Multi-Granular Spatio-Temporal Token Merging for Training-Free
  Acceleration of Video LLMs
Video large language models (LLMs) achieve strong video understanding by
leveraging a large number of spatio-temporal tokens, but suffer from quadratic
computational scaling with token count. To address this, we propose a
training-free spatio-temporal token merging method, named STTM. Our key insight
is to exploit local spatial and temporal redundancy in video data which has
been overlooked in prior work. STTM first transforms each frame into
multi-granular spatial tokens using a coarse-to-fine search over a quadtree
structure, then performs directed pairwise merging across the temporal
dimension. This decomposed merging approach outperforms existing token
reduction methods across six video QA benchmarks. Notably, STTM achieves a
2times speed-up with only a 0.5% accuracy drop under a 50% token budget, and
a 3times speed-up with just a 2% drop under a 30% budget. Moreover, STTM is
query-agnostic, allowing KV cache reuse across different questions for the same
video. The project page is available at https://www.jshyun.me/projects/sttm.
68708156c8391850d6097869
Jeongseok Hyun
claimed_verified
2025-07-11T08:00:01.307Z
6513030fb3a463e17df56edd
/avatars/867bd4316b2de758654ad3a84ea868c1.svg
Hyun, Jeongseok
user
js-hyun
68708156c8391850d609786a
Sukjun Hwang
68708156c8391850d609786b
Su Ho Han
68708156c8391850d609786c
Taeoh Kim
68708156c8391850d609786d
Inwoong Lee
68708156c8391850d609786e
Dongyoon Wee
68708156c8391850d609786f
Joon-Young Lee
68708156c8391850d6097870
Seon Joo Kim
68708156c8391850d6097871
Minho Shim
Multi-Granular Spatio-Temporal Token Merging for Training-Free
  Acceleration of Video LLMs
Video large language models (LLMs) achieve strong video understanding by
leveraging a large number of spatio-temporal tokens, but suffer from quadratic
computational scaling with token count. To address this, we propose a
training-free spatio-temporal token merging method, named STTM. Our key insight
is to exploit local spatial and temporal redundancy in video data which has
been overlooked in prior work. STTM first transforms each frame into
multi-granular spatial tokens using a coarse-to-fine search over a quadtree
structure, then performs directed pairwise merging across the temporal
dimension. This decomposed merging approach outperforms existing token
reduction methods across six video QA benchmarks. Notably, STTM achieves a
2times speed-up with only a 0.5% accuracy drop under a 50% token budget, and
a 3times speed-up with just a 2% drop under a 30% budget. Moreover, STTM is
query-agnostic, allowing KV cache reuse across different questions for the same
video. The project page is available at https://www.jshyun.me/projects/sttm.
A training-free method merges spatio-temporal tokens in video large language models to reduce computational cost while maintaining accuracy.
spatio-temporal tokens token merging quadtree structure directed pairwise merging video QA benchmarks KV cache reuse