Existing VLMs have achieved strong performance in video understanding, yet they struggle with long-video spatiotemporal reasoning when target objects become invisible, often mistaking "invisible" for "unknown". We define this challenge as hidden-state spatiotemporal reasoning: inferring object states during prolonged invisible intervals from context interactions. To address this, we propose StateTrace, a novel object-centric framework that endows VideoLLMs with an explicit mechanism for hidden state reasoning in long videos. StateTrace builds a reusable spatiotemporal state memory that organizes object trajectories, inter-object relations, and state-transition events into a structured reasoning substrate. At inference time, it retrieves question-relevant state-evolution trajectories and converts them into compact reasoning cues, enabling the model to explicitly reason about why an object disappears, how its state evolves while invisible, and whether that state should persist at query time. We further build HSR-Bench, a diagnostic benchmark for hidden-state reasoning, containing 1,427 video-QA samples from 1,384 unique videos. Extensive experiments across multiple VideoLLMs show that StateTrace consistently improves performance on both public benchmarks and HSR-Bench (e.g., improving VideoLLaMA3 from 39.6 to 64.2 on HSR-Bench).
Mengjie Zhang, Qihui Zhu, Tao Zhang +10cs.CV cs.CL
Video large language models (VideoLLMs) achieve strong video understanding performance, but their inference remains expensive due to the large number of redundant spatio-temporal visual tokens in long videos. Existing token pruning methods alleviate this cost by reducing redundant tokens, yet most of them rely on segment-level local pruning, where videos are partitioned into isolated segments and tokens are selected independently within each segment. Such designs may under-preserve short but semantically dense segments and discard tokens that appear non-salient locally but remain critical from a global perspective. To address this issue, we propose GSTEP (Global Spatio-Temporal Density Pruning), a plug-and-play pruning framework that models video as a continuous spatio-temporal information flow. GSTEP constructs a token-level spatio-temporal density by combining a continuous temporal density, obtained from a smoothed centered frame-level change signal, with intra-frame spatial density, and then performs global token sampling by jointly balancing information density and coverage. Extensive experiments on multiple VideoLLMs and public benchmarks demonstrate that GSTEP consistently achieves strong accuracy-efficiency trade-offs and generalizes well across model architectures and evaluation settings. On LLaVA-OneVision-7B, GSTEP prunes 75% of visual tokens, preserves up to 100.2% of the original average performance across benchmarks, and achieves a 1.17 end-to-end speedup.
Streaming VideoLLMs process frames causally while visual tokens grow continuously, making compression essential for controlling prefilling latency and memory. Existing training-free methods independently rank tokens, ignoring marginal-gain interactions among retained tokens. We argue that streaming video token compression should instead be formulated as set selection, where each candidate is valued by what it adds beyond the tokens already retained. Unlike existing set-wise methods designed for offline tasks, streaming makes causal, frame-by-frame pruning decisions, so modeling cross-frame interactions requires an explicit historical reference. This creates a reference-set dilemma: the reference must adequately represent previously conveyed content while remaining bounded for real-time inference. We introduce NovaCov, to our knowledge the first training-free, plug-and-play set-wise token compressor designed for streaming video. NovaCov maintains a capacity-bounded, recency-weighted Historical Reference Bank and optimizes a dual-branch submodular coverage objective that preserves representative current-frame content while prioritizing information insufficiently covered by history. Both branches are facility-location functions, so greedy selection retains the classical (1-1/e) approximation guarantee. Across streaming and offline benchmarks, NovaCov outperforms existing training-free compression methods, retaining 99.6% of ReKV accuracy while reducing LLM prefilling latency by 46%.