Video language models answer questions about video by turning every frame into a grid of image patches ("tokens") and feeding them to a large language model. Two choices dominate the cost. The first is how finely each frame is cut into patches. The second is which of the resulting tokens survive pruning. Adjacent frames are nearly identical, so most tokens are redundant. The few that matter, such as a hand closing on a tool or a small object changing state, are often exactly the ones a coarse grid blurs away. Current systems make the two choices separately. They pick a fixed patch grid, then prune tokens on that grid. When they prune "diversely," they use a probabilistic tool that only knows how to push similar tokens apart.
We propose making both choices in one step. Every frame is offered at several spatial resolutions at once, so a region can be represented by one coarse token or by its four finer children. A single probabilistic subset selector, which can express both attraction and repulsion between tokens, then decides which tokens to keep. Repulsion removes temporal duplicates and removes a coarse token whose fine children are already kept. Attraction keeps fine sub-patches together when they jointly describe a moving boundary or an interacting pair. The resolution of each region in each frame is never set by hand. It is whatever the selected subset happens to contain.
Core Claim
A determinantal point process (DPP) is a probability distribution over subsets in which a set's probability is the determinant of a kernel submatrix. With the usual symmetric kernel, similar items lower each other's joint probability, so the model can only express repulsion (Determinantal Point Processes for Machine Learning). The closest existing work, CDPruner, uses exactly this. It builds a symmetric DPP over a flat, fixed patch grid, conditions it on the text instruction, and reports keeping 98.6% of performance while pruning 62% of tokens on long-video tasks.
Our claim differs in two ways. It changes what the candidate items are (a multi-resolution hierarchy, not a flat grid), and it changes what the selector can express (attraction as well as repulsion). The second change only becomes useful because of the first. On a flat grid, "two tokens must appear together" is a weak signal. On a hierarchy, it is precisely the signal that says "this region needs fine resolution here and now."
The tool for attraction is the nonsymmetric DPP of Learning Nonsymmetric Determinantal Point Processes. It writes the kernel as $L = S + A$, with $S$ symmetric low-rank and $A$ skew-symmetric. For two items $i, j$, the pair's unnormalized probability is
$$\det L_{\{i,j\}} = L_{ii}L_{jj} - S_{ij}^2 + A_{ij}^2,$$
so the skew term $A_{ij}$ can lift a pair above independence (attraction), while the similarity term $S_{ij}$ pushes it below (repulsion).
On Amazon baskets, this model learned about 71–80% of within-category interactions as positive and 95–97% of cross-category interactions as negative. It raised mean percentile rank from 60.61 to 75.09 over a symmetric DPP. Nobody has tested whether the same split appears among video tokens. We hypothesize that it does: static background tokens across time are substitutes, while fine tokens along a moving contact region are complements.
Research Program
Ground set. Each sampled frame is encoded once at the vision encoder's high input resolution. Patch features are then average-pooled into a quadtree with two or three levels, from fine patches up to cells four or sixteen times larger. Every node at every level, in every frame, is a candidate item. Pooling is cheap.
We are explicit about where the savings come from. The method does not reduce vision encoder cost. It reduces language-model context, which is where AdaCodec locates the latency bottleneck: time-to-first-token was 9.26s with dense frames and 1.62s with its compact code.
Kernel. We use the low-rank parameterization of Scalable Learning and MAP Inference for Nonsymmetric Determinantal Point Processes, $S = VV^\top$ and $A = BCB^\top$ with block-diagonal skew-symmetric $C$. That paper gives linear-in-$M$ training memory and an $O(M)$ greedy method for finding the most probable subset, where $M$ is the number of candidate tokens. This matters because $M$ reaches tens of thousands per video.
Unlike the basket setting, the rows of $V$ and $B$ are not free parameters per item. A small network computes them from four inputs: the token's visual feature, its quadtree level, its position, and its temporal residual (feature change from the previous frame at the same location, in the spirit of AdaCodec's predictive cost). Following CDPruner, the kernel is rescaled by a per-token quality term derived from similarity to the instruction, $L = D(S+A)D$. One network therefore serves every video.
Supervision. Unlike CDPruner, the kernel must be learned, and this is the main design risk. On a held-out training pool of instruction–video pairs, we run an expensive greedy search with the frozen language model. The search adds candidate tokens one at a time and keeps whichever most increases the answer's log-likelihood, until it reaches the budget. The resulting subsets are treated as observed "baskets," and the kernel network is fit by NDPP maximum likelihood. At test time, the oracle is gone and only the cheap greedy MAP runs.
The greedy guarantees for NDPPs require the smallest singular value of $L$ to exceed one. We add the regularizer suggested in that line of work and report how often the condition holds.
Long videos. For the 30–60 minute split of Video-MME, the full multi-scale ground set does not fit comfortably in memory. Here we replace offline greedy with the one-pass stash algorithms of One-Pass Algorithms for MAP Inference of Nonsymmetric Determinantal Point Processes, feeding frames in temporal order. That paper warns that one-pass inference degrades under strongly clustered orderings, and video is the clustered ordering par excellence. We therefore treat this as a secondary, explicitly risky extension rather than part of the core claim.
Baselines
Reference points. The do-nothing reference is the backbone, LLaVA-OV-7B, with all tokens at its default resolution. DyCoke reports 58.0 average on MVBench for this setup. The naive budget-matched reference is uniform spatial downsampling of every frame to the target token count. All methods share the frozen backbone, the same sampled frames, and the same final language-model token budgets (25%, 38%, and 15% of full).
Strongest training-free competitor. This is CDPruner on the standard flat grid, the most direct prior use of a DPP for this task, with its reported 98.6%-at-62%-pruned figure. We rerun it ourselves at identical budgets rather than relying on that aggregate.
Temporal-merging competitor. DyCoke, which reports 57.5 on MVBench at $K=0.7$ with 1.54× speedup, represents heuristic temporal merging plus a recovery cache.
Learned scorer with structure. An STTS-style learned scorer (Efficient Video Transformers with Spatial-Temporal Token Selection) rates frames and contiguous anchors independently. We retrain it on the same oracle subsets and training pool as our kernel, so learning alone is not the difference.
Ablations. Two ablations isolate the proposal's ingredients, and they are the experiments we care most about. The first runs a symmetric DPP (set $A=0$) on the same multi-resolution ground set, trained the same way. This isolates attraction. The second runs our full NDPP on the flat single-resolution grid. This isolates the hierarchy.
What counts as winning. We beat the field if three things hold. First, at matched budgets the full method exceeds re-run CDPruner on MVBench and Video-MME by more than seed-level variation. Second, it exceeds the symmetric multi-scale ablation. Third, its gains concentrate on fine-motion and small-object questions. If the symmetric multi-scale ablation matches the full method, the honest conclusion is that the hierarchy, not attraction, carries the result.
Why not just…?
Why not just run CDPruner on a multi-resolution ground set? This is the most serious alternative, and it is literally our first ablation. Our argument against it is structural. A symmetric kernel penalizes keeping two aligned fine children of the same moving region. It therefore tends to keep one fine patch per region and a coarse parent elsewhere, which is exactly the "mistaking synergy for redundancy" failure documented on disjoint-group data. There, the symmetric DPP scored AUC 0.5 against 0.7 for the nonsymmetric one (Learning Nonsymmetric Determinantal Point Processes). Whether video tokens behave like those baskets is an empirical question that the ablation settles directly.
Why not just refine regions where the temporal residual is large, with no point process? A PointRend-style rule (PointRend: subdivide only where the coarse pass is uncertain) driven by AdaCodec's predictive cost is cheap and plausible. We implement it as a baseline with the same budgets. Our expectation is that it fails in two cases. One is static but query-relevant small objects, where the residual is zero yet detail is needed. The other is repetitive motion, such as waving foliage, where the residual is high but the content is redundant. PointRend's own limitation also applies: refinement cannot recover what the coarse pass missed entirely. If this heuristic matches us overall, we will report that the point process earns its cost only on the query-relevant-static subset, or not at all.
Why not just keep the most-attended tokens? CDPruner shows that top-attention pruning keeps clusters of near-duplicates. DyCoke shows that one-shot attention pruning deletes tokens needed later in decoding. We include it at matched budgets only as a sanity floor.
Proposed Experiments
Main evaluation. We evaluate on MVBench (20 fine-grained temporal tasks, MVBench), Video-MME broken down by short, medium, and long duration, and Charades-STA temporal grounding. Grounding is where fine temporal detail should matter most. The strongest reported figure on Charades-STA in our file is 44.3 mIoU zero-shot for Qwen2-VL-7B with T2SGrid. That method packs frames into composite images and degrades at 4×4 because of uniform per-cell downsampling, a failure our method should avoid by construction. To compare against it fairly, we additionally run our selector on Qwen2-VL-7B. We report accuracy at each budget, time-to-first-token, and peak memory.
Mechanism diagnostic. Mirroring the basket analysis, we measure the fraction of learned pairwise interactions that are positive, split by token-pair type. The pair types are: fine tokens sharing a high-residual coarse parent; temporally adjacent static tokens; and parent–child pairs. The hypothesis predicts mostly positive values for the first type and mostly negative values for the other two. If the learned interactions come out uniformly negative, the attraction story is false regardless of the accuracy numbers.
We also visualize the induced per-frame resolution maps. We report how often they become fine on frames that MVBench's motion-direction and action-sequence tasks depend on.
Decisive checks. The project's thesis stands or falls on three comparisons. The first is full method against the symmetric multi-scale ablation, which tests attraction. The second is full method against the residual-quadtree heuristic, which tests whether a point process is needed at all. The third is the gap on fine-motion MVBench tasks and the short-video Video-MME split, compared with the gap on coarse scene-level questions. If gains appear only in aggregate and not on the fine-detail slices, the mechanism we claim is not the one doing the work.
References
- Determinantal Point Processes for Machine Learning
- Beyond Attention or Similarity: Maximizing Conditional Diversity for Token Pruning in MLLMs
- Learning Nonsymmetric Determinantal Point Processes
- AdaCodec: A Predictive Visual Code for Video MLLMs
- Scalable Learning and MAP Inference for Nonsymmetric Determinantal Point Processes
- Video-MME: The First-Ever Comprehensive Evaluation Benchmark of Multi-modal LLMs in Video Analysis
- One-Pass Algorithms for MAP Inference of Nonsymmetric Determinantal Point Processes
- DyCoke: Dynamic Compression of Tokens for Fast Video Large Language Models
- Efficient Video Transformers with Spatial-Temporal Token Selection
- PointRend: Image Segmentation As Rendering
- MVBench: A Comprehensive Multi-modal Video Understanding Benchmark
- T2SGrid: Temporal-to-Spatial Gridification for Video Temporal Grounding