Static Scenes Are Separable: Kronecker Kernels as a Model of Temporal Redundancy in Video Tokens

A video language model, which is a large language model that reads a video as a long sequence of image-patch "tokens," spends most of its context on content it has already seen. A wall, a table or a road appears in nearly the same place in hundreds of consecutive frames. Current token-pruning methods remove this repetition in two ways. Some compare each frame with the one just before it. Others run expensive diversity selection inside short windows. Neither has a global, explicit account of what is redundant. This note proposes such an account. Unchanging scene content is exactly the part of the token-similarity matrix that splits into a product of a "which frames look alike" matrix and a "which patch positions look alike" matrix. That kind of product is a Kronecker product, the structure that fast Gaussian-process and covariance methods are built on. Whatever the product cannot explain (moving hands, objects entering, cuts to new content) is the informative part.

The proposal fits the similarity matrix of all video tokens as a sum of a few Kronecker products plus a residual. It spends a small share of the token budget on a compact summary of the separable scene, and spends the rest on residual tokens chosen with an instruction-aware diversity criterion. In two sentences: temporal redundancy shows up as low "separation rank" in the token kernel. Measuring it globally rather than frame to frame should let a pruner drop more tokens on long videos without losing the brief events that questions are about.

Core Claim

Write the visual tokens of a video as features $x_{t,s} \in \mathbb{R}^d$ for frame $t \in \{1..T\}$ and patch position $s \in \{1..S\}$. Let $K$ be their $TS \times TS$ cosine-similarity kernel. The claim is that, for real videos and especially after motion compensation, $K$ is well approximated by

$$K \approx \sum_{r=1}^{R} A_r \otimes B_r + \Gamma,$$

Here each $A_r$ is a $T \times T$ temporal factor, each $B_r$ is an $S \times S$ spatial factor, $R$ is small (we expect under 5), and $\Gamma$ is a residual whose energy is concentrated on a small fraction of tokens. Three things follow. The residual energy of token $(t,s)$, the norm of its row of $\Gamma$, is a principled per-token novelty score. The temporal factors $A_r$ mark segments of frames that share a scene layout. This holds even when those frames are not adjacent, for example when a shot returns after a cut. Finally, the decomposition is cheap enough to fit over the whole video, so no windowing is needed.

This is the robust spatio-temporal covariance model of Robust Kronecker Product PCA for Spatio-Temporal Covariance Estimation, which separates a low-separation-rank part from sparse anomalies in sensor data. We supply its method, but move it from sample covariances of stationary sensors to similarity kernels of deep video features. We also reinterpret its "outliers" as the signal rather than the noise.

The work closest to this one uses Kronecker structure differently. Kronecker Determinantal Point Processes factors a diversity kernel as a pure product $L_1 \otimes L_2$ to speed up sampling and learning. That paper names video summarization as an application but never runs it. A pure product kernel would erase exactly the content-specific, non-separable structure that marks events, so we do not use it as the selection kernel. Kronecker Mask and Interpretive Prompts are Language-Action Video Learners (CLAVER) builds attention masks as $M_T \otimes M_S$ but keeps every token. Beyond Attention or Similarity: Maximizing Conditional Diversity for Token Pruning in MLLMs (CDPruner) runs instruction-conditioned determinantal selection on the flattened token kernel. It needs local windows on long video, and it treats a background patch repeated across 300 frames as 300 candidates. Our contribution is the decomposition and what it buys. CDPruner's selection rule is reused, not replaced.

Research Program

The first component fits the decomposition without ever forming $K$. The Pitsianis–Van Loan rearrangement turns a sum of Kronecker products into a low-rank matrix of size $T^2 \times S^2$. Applying that rearranged operator to an $S \times S$ matrix $V$ yields, entry by entry,

$$[\mathcal{R}(K)\,V]_{t,t'} = \operatorname{tr}\!\left(X_t^\top V X_{t'}\right),$$

where $X_t \in \mathbb{R}^{S \times d}$ stacks frame $t$'s token features. Each product therefore costs about $T S^2 d + T^2 S d$ operations instead of the $T^2 S^2 d$ needed to build the full kernel. A few Lanczos iterations then recover the top $R$ Kronecker terms. To stop moving objects from contaminating the scene factors, we alternate between this fit and a soft-thresholding step that moves high-residual tokens into $\Gamma$, in the spirit of the low-rank-plus-sparse solver of the Robust KronPCA paper. We avoid that paper's full SVDs in the rearranged space, which it flags as the bottleneck at scale.

The second component handles the known weakness of separable models. When the camera pans, the same wall moves to different patch positions, and pure separability fails. The open-problems summary of the research file lists exactly this non-separable motion as the main source of bias. Before factoring, we re-index patch positions per frame using a global patch-grid shift. This shift is estimated either from feature matching between frames or from codec motion vectors, as in Compressed Video Action Recognition and AdaCodec: A Predictive Visual Code for Video MLLMs. Patches that fall off the aligned grid are treated as missing entries. This is the same "holes in a grid" situation that Fast Near-GRID Gaussian Process Regression handles with low-rank corrections; here it amounts to masking those entries in the trace products.

The third component is the pruner itself. It is training-free and plugs in before the language model. The temporal factors $A_r$ are clustered into scene segments. For each segment we emit one set of position-wise merged tokens: the average of aligned low-residual tokens across that segment, placed at the segment's first frame. This is a global analogue of the adjacent-frame merging in DyCoke. The remaining budget goes to high-residual tokens, chosen by CDPruner's greedy conditional-diversity rule over the residual candidates only. The split between the two pools is set by the fraction of kernel energy left in $\Gamma$, so a static lecture video gets few event tokens and a cooking video gets many. Because the event candidate pool is small, CDPruner's selection can run over the whole video rather than in windows.

Baselines

The naive reference points are the full-token model and uniform frame subsampling at matched token count. Uniform subsampling is the regime Less Is More: ClipBERT for Video-and-Language Learning via Sparse Sampling showed can work well on short clips. Video-MME reports that even Gemini 1.5 Pro loses 14.3% accuracy from short to long videos, which is where we expect sparse sampling to fail.

The first strong baseline is DyCoke, which merges similar tokens across consecutive frames and prunes the cache dynamically. It is the most direct competitor on temporal redundancy specifically. On LLaVA-OneVision it reports an MVBench average of 57.5 at 0.7 retention, against 58.0 for the full-token model. We will run it on the same backbone, frames and budgets using its released settings.

The second strong baseline is CDPruner, the strongest diversity-based method. It reports keeping 98.6% of performance while pruning 62% of tokens on video inputs above 10,000 tokens. The file has no reported CDPruner or DyCoke numbers on Video-MME (no reported result found on Lacuna for those), so we will measure them ourselves. CDPruner will be run with its default window size and with the largest window that fits in the same memory. That way, it is not handicapped on the very axis we claim to improve.

We also include AdaCodec as a codec-side reference. It reports up to an 84.6% token reduction. Because it changes the visual encoding and requires training, we compare against it only at matched token budgets and report this caveat.

Beating these baselines means higher accuracy at equal visual-token count and no worse prefill latency. This applies at 25% and 15% retention on Video-MME long and on LongVideoBench. On MVBench, beating them means staying within 0.5 points of the full-token 58.0 at retention below DyCoke's 0.7.

Three ablations isolate the key ingredient. In the first, the rank is fixed at $R=1$ with $A_1$ forced to be all ones. This is plain per-position temporal-mean subtraction, i.e. background subtraction, and it tests whether the Kronecker structure matters at all. In the second, motion compensation is removed. In the third, the residual pool is filled by residual magnitude alone instead of by diversity selection.

Why not just…?

Why not just merge each token with its neighbor in the previous frame, as DyCoke does? For a static camera with continuous shots, this will capture most of the same redundancy, and we expect it to come close to our method. The difference should appear in two places. The first is content that recurs non-adjacently, such as shot–reverse-shot dialogue or a return to the workbench after a cut. Adjacent-frame merging re-pays for such content every time, while a temporal factor $A_r$ groups it. The second is slow pans, where position-wise comparison fails without alignment. We will report results stratified by measured camera motion and by shot-recurrence rate. If our gains vanish in both strata, the global model is not worth its cost.

Why not just run CDPruner with bigger windows? This is the most serious alternative. Diversity selection already discourages picking near-duplicate tokens. Our answer rests on two measurable things. One is cost: the full flattened kernel grows with $(TS)^2$, while our fit grows with $TS^2 + T^2S$ per Lanczos step. The other is how the budget is split: diversity alone does not know that a static video deserves few tokens and an eventful one many. If CDPruner with a full-video window matches our accuracy at similar latency on the 30–60 minute Video-MME split, the decomposition contributes only speed, and we will say so.

Why not just subtract the per-position temporal mean and keep the high-residual tokens? This is the $R=1$, constant-time-factor ablation. It is the cheapest version of the idea and may capture much of the effect in single-shot videos. The rank sweep is designed to show whether additional Kronecker terms, which represent multiple scene layouts over time, buy accuracy on multi-shot long videos. If $R=1$ matches higher rank everywhere, the paper becomes "background subtraction is a strong pruner," which is still a useful finding.

Proposed Experiments

The first experiment is a diagnostic: is the claim even true? On held-out videos from Video-MME (all three duration bands), MVBench and LongVideoBench, we encode tokens with the LLaVA-OneVision vision tower. We then measure the fraction of kernel energy captured by $R = 1..8$ Kronecker terms, with and without motion compensation. We also check whether high-residual tokens overlap the spatio-temporal regions that MVBench's motion-centric questions ask about. If fewer than about 70% of the energy is captured at $R \le 4$ on long videos, or if residual mass is not concentrated in a small token fraction, the premise fails and we stop.

The main experiment is training-free pruning on LLaVA-OneVision. Retention ranges from 50% down to 10%, at a fixed number of input frames, and is evaluated on MVBench, Video-MME (frames-only track, reported per duration band) and LongVideoBench. Prefill latency and peak memory are measured on the same GPU for every method.

The decisive check is the Video-MME long band at 15% retention. Our method should beat both DyCoke and the largest-window CDPruner there. It should also beat the $R=1$ background-subtraction ablation on the multi-shot subset, which would show that the separable structure, and not just a novelty score, is doing the work. A secondary check plots per-video residual-energy fraction against the accuracy loss of uniform sampling. If our budget split is right, videos with high residual energy should be exactly those where uniform sampling hurts most.