A video large language model (a language model that reads a video as a long sequence of image-patch "tokens") spends most of its time and memory on tokens that repeat. Consecutive frames show the same background, so the same information is fed in many times. Current training-free compressors decide which tokens to keep with local rules. One cuts the video wherever adjacent frames differ by more than a threshold. Another merges tokens that look alike in neighbouring frames. Neither looks at the user's question. We propose to treat "how many tokens does each stretch of video get, and where do the stretches begin and end" as a single optimization problem. Its objective is how much of the original video is lost, with each token weighted by how relevant it is to the question. The problem is solved exactly by dynamic programming, which breaks it into overlapping subproblems and reuses their answers.
Solving this program exactly is expensive. Our second claim is that it is cheap enough to run separately for every question inside the prefill stage (the initial forward pass over the video before the model generates text) once it is written as a batched min-plus product. In that product, "multiply" becomes addition and "sum" becomes minimum, so the dynamic programming step becomes a matrix-style operation that GPUs execute well. Temporal redundancy supplies the problem. Parallel dynamic programming is what makes the exact, question-specific solution affordable at serving time.
Core Claim
Take a video with $T$ frames, each encoded into visual tokens, and a total token budget $B$. A plan splits the frames into contiguous segments of at most $L$ frames. It then gives segment $[a,b]$ some number $k$ of merged tokens. We define the segment cost $c_q(a,b,k)$ as the relevance-weighted distortion of representing all tokens in frames $a$ through $b$ by $k$ merged tokens. Here each token's squared distance to its merged representative is multiplied by $1+\beta r_q(x)$, where $r_q(x)$ is the similarity between token $x$ and the question $q$ and $\beta$ sets how much the question matters. Because the question enters only through per-token weights, the total cost adds up over segments, and the best plan satisfies
$$V(t,b) = \min_{1\le \ell \le L,\; 0\le k \le b} \Big[ V(t-\ell,\, b-k) + c_q(t-\ell+1,\, t,\, k) \Big],$$
where $V(t,b)$ is the lowest cost of covering the first $t$ frames with $b$ tokens. Each row $t$ depends only on earlier rows. Within a row, the update is a min-plus convolution over the budget axis, and it is fully parallel across $b$, $\ell$, $k$ and across a batch of queries.
We claim two things. First, at the same token budget, the exact question-weighted plan beats greedy threshold segmentation with proportional budgets on question-answering accuracy. The gains should be largest on questions about brief or low-salience content. Second, a GPU min-plus kernel makes the extra cost of planning small compared with the prefill time it saves, and a CPU solver does not.
Prior work motivates both halves of this claim. FastVID groups frames by thresholding adjacent similarity and then prunes by density peaks and vision-encoder attention, without looking at the question. The research file identifies this as the failure mode when questions refer to background details. DyCoke merges tokens by pairwise comparison of adjacent frames. It repairs mistakes during decoding with a "recycle bin" of evicted tokens, but it never plans across many frames at once. FOCUS is question-aware, but it selects whole frames with a bandit that treats clips as independent, and it misses one- to two-second actions during its coarse pass. None of these optimizes a global objective. Conversely, the closest dynamic programming work does not touch inference-time compression. Lu et al. select summary keyframes with a one-dimensional CPU dynamic program over handcrafted saliency features. Hadji et al. and VT-TWINS use soft dynamic time warping only as a training loss. Our program has two decisions per step, segmentation and token count, and runs at inference over transformer tokens.
Research Program
The method has three parts.
The first part builds the cost table. For every candidate segment of length up to $L$, we run a single agglomerative merge of its tokens. This is a nested merging similar to bipartite token merging, so one pass produces the weighted distortion curve for every $k$ at once. With $T=320$ and $L=16$ there are about 5,000 segments. Each segment's merge is independent, so all of them run as one batched GPU job. Question relevance comes from cosine similarity between visual tokens and the text embedding of the question in the vision encoder's joint space, and it is computed once per token. We will check empirically whether the curves are convex in $k$. If they are, the min-plus convolution admits faster exact algorithms. If they are not, we fall back to the direct form.
The second part is the solver kernel. We follow the reformulation of Zhao et al., who rewrite forward dynamic programming as batched min-plus matrix-vector products. They parallelize across scenarios, transitions and actions using warp- and block-level reduction trees, and report speedups of 20× over 8-thread CPUs on vehicle routing and of 22,600× over multi-threaded CPUs on inventory routing. Their problems are layered graphs. Ours is also layered (row $t$), with segment length $\ell$ and token count $k$ playing the role of actions and concurrent user queries playing the role of scenarios. The method is therefore reused directly. What we add is the application and a back-pointer store for recovering the plan. We avoid the anti-diagonal wavefront sweeps used in d²p, because rows of our lattice depend only on strictly earlier rows. The file notes that sequential wavefront launches dominate run time on long lattices, and our row-by-row structure needs only $T$ launches, which can be fused.
The third part turns the plan into tokens. Each segment's $k$ merged tokens take the mean timestamp of the frames they summarize, so temporal order is preserved. This is the property FastVID argues matters. The tokens are then passed to an unchanged video LLM. The whole pipeline needs no training. The only tuned quantities are $\beta$ and $L$.
The scale is large enough that the speed question is real, not decorative. With roughly 200 tokens per frame in LLaVA-OneVision, 320 frames and budgets in the thousands, a single query's program involves billions of min-plus operations. That is too slow for a CPU at interactive latency but should take milliseconds on a GPU. Whether it actually does is something we will measure, not assume.
Baselines
The naive reference point is uniform frame subsampling to the token budget with no merging. We also include the full-token model as the accuracy ceiling. Both are run on LLaVA-OneVision-7B with identical prompts and decoding.
The strongest existing method is FastVID, run with its released settings and with its thresholds tuned on the same held-out split and the same tuning budget as our $\beta$ and $L$. On LLaVA-OneVision-7B, the authors report retaining 98.0% of full-token accuracy averaged over MVBench, VideoMME, LongVideoBench, MLVU and ActivityNet-QA. They achieve this while pruning 90.3% of visual tokens, cutting FLOPs to 8.3% and speeding up prefill by 7.1× (FastVID). Beating FastVID means higher accuracy retention at the same 90.3% pruning rate, or equal retention at a higher pruning rate, with end-to-end prefill time (planning included) no worse than FastVID's.
DyCoke is the second compression baseline. It reports 57.5 on MVBench against a full-token 58.0 at 0.7 retention (DyCoke). FOCUS is the question-aware frame-selection baseline. It reports an 11.9% gain over uniform sampling on LongVideoBench videos longer than 20 minutes while using 1.6% of frames (FOCUS). We will run FOCUS at a matched token count.
Two ablations isolate the key ingredients. The first keeps our relevance-weighted cost but replaces the exact program with FastVID-style threshold segmentation and budgets proportional to segment size. This measures the value of global optimality alone. The second keeps the exact program but sets $\beta=0$. This measures the value of conditioning on the question alone. A third check runs the identical program on CPU to establish what the GPU kernel buys.
Why not just…?
Why not just add question relevance to FastVID's pruning step and keep its greedy segmentation? This is the most serious threat, and it is exactly our first ablation. If threshold segmentation plus relevance-weighted pruning matches the exact program, then global planning adds nothing, and we will report the question weighting as the contribution. We expect the exact program to win where the greedy method fails structurally. A threshold cannot give a two-second relevant event more tokens than a long static stretch, because it allocates budget by segment size rather than by weighted distortion. We will measure the optimality gap of the greedy plan under our own objective to confirm that the gap is real before attributing any accuracy difference to it.
Why not just run the dynamic program on CPU, or on a coarsened budget grid? If the budget axis can be quantized to, say, 64 levels without losing accuracy, a CPU solver may be fast enough, and the GPU kernel becomes optional engineering. We will sweep the grid resolution and report accuracy alongside planning latency for both CPU and GPU. The parallel-dynamic-programming contribution stands only if fine budget grids, long frame horizons or batched concurrent queries push CPU planning past the prefill time it saves.
Why not just pick the top-$k$ tokens by similarity to the question, ignoring time? This drops temporal structure and coverage. It tends to keep many near-duplicate copies of the most question-like object and to lose context. We include it as a baseline at matched budgets. It also tests whether distortion, rather than relevance alone, is needed in the cost.
Why not just train a learned token scorer? STTS learns temporal and spatial selection with a small scorer. It saves 33% of GFLOPs at 50% token retention, losing under 0.7% accuracy on Kinetics-400. That requires end-to-end training per backbone and operates at far milder compression than the roughly 90% pruning regime relevant here. Our method remains training-free and is meant to be compared with other training-free compressors.
Proposed Experiments
The main evaluation uses LLaVA-OneVision-7B on MVBench, Video-MME (split into short, medium and long), LongVideoBench and MLVU. Token retention is set at 10%, 25% and 50%. Metrics are accuracy, accuracy retention relative to full tokens, end-to-end prefill latency with planning time reported separately, and peak memory. We also repeat FastVID's extrapolation setting, compressing 320 frames into a 32-frame token budget, because the planning problem is largest there.
The decisive check is a probe for brief events. We insert one- to two-second clips into long Video-MME and LongVideoBench videos and ask questions answerable only from the inserted clip. Our method should hold accuracy where FastVID and FOCUS degrade. Its $\beta=0$ ablation should degrade along with them, which shows that the gain comes from conditioning on the question rather than from merging. A second check measures planning latency against batch size and frame count, on GPU and CPU, to locate the regime where the min-plus kernel is necessary.
We commit in advance to the following reading of results. If the greedy ablation matches the exact program on both the probe and the standard benchmarks, we conclude that global optimality is unnecessary for this task, and the paper reduces to a study of question-weighted merging.
References
- FastVID: Dynamic Density Pruning for Fast Video Large Language Models
- DyCoke: Dynamic Compression of Tokens for Fast Video Large Language Models
- FOCUS: Efficient Keyframe Selection for Long Video Understanding
- Predicting Important Objects for Egocentric Video Summarization.
- Representation Learning via Global Temporal Alignment and Cycle-Consistency
- Video-Text Representation Learning via Differentiable Weak Temporal Alignment
- From Sequential to Parallel: Reformulating Dynamic Programming as GPU Kernels for Large-Scale Stochastic Combinatorial Optimization
- d$^2$p: Structured Soft Attention Is All You Need
- Efficient Video Transformers with Spatial-Temporal Token Selection