Video question-answering models can only look at a few dozen frames of a video that may contain a hundred thousand. Recent systems spend extra compute at answer time to choose those frames better. They score candidate frames with a vision-language model and then look more densely around the promising ones. When the scorer is right, this works well. When the scorer is wrong early on, the system stops looking where the answer actually is, and no later compute can recover it.
We propose a frame-search procedure that borrows its structure from the convergence theory of diffusion models (generators that turn noise into data by repeated denoising). That theory shows such samplers reach arbitrary data distributions without assuming the data is smooth or well-behaved. It gets there in two ways. It first blurs the problem so that every intermediate stage is tractable. It then charges the final error only to the average error of the learned guide along the path, not to its worst-case error. We carry both ideas over to time. Each round of frame search samples from a temporally blurred relevance map that is mixed with a fixed share of evenly spaced frames, and the blur shrinks round by round. The evenly spaced share gives a guarantee that holds for any video and any scorer: no event longer than a stated duration can be missed. The adaptive share means that the better the scorer, the closer the search gets to an oracle.
Core Claim
Any frame-search method that relies entirely on the model's own relevance judgments can be driven arbitrarily far from correct by a scorer error made early in the search. Pure random probing avoids this failure but wastes the budget on irrelevant footage. A coarse-to-fine schedule with a stratified exploration floor and an annealed smoothing width does three things at once. First, it guarantees that every event lasting at least $T/(\lambda k)$ frames is observed. Here $T$ is the video length, $k$ is the per-round frame budget, and $\lambda$ is the fraction of each round reserved for evenly spaced frames; the guarantee follows because evenly spaced frames hit every interval longer than their spacing. Second, its excess error over an oracle selector is bounded by the scorer's average error under the search's own sampling distribution. Third, as a result, it is never much worse than uniform sampling and approaches the best adaptive selector when the scorer is good.
The target theorem has the same three-part shape as the error decomposition in Sampling is as easy as learning the score. That paper splits sampling error into forward-process mixing, time discretization, and average score error. In our setting the bound reads
$$ P(\text{miss}) \;\le\; \mathbb{1}[w < T/(\lambda k)] \;+\; \sum_{r=1}^{R} \epsilon_{\text{disc}}(h_{r-1}, h_r) \;+\; C\,\mathbb{E}_{q_r}\big[\,|\hat s_r - s_r|\,\big], $$
The terms are defined as follows. $w$ is the duration of the evidence an answer needs, which plays the role of EgoSchema's "temporal certificate length", the minimal window a human needs to verify the answer. $h_r$ is the smoothing width at round $r$ out of $R$ rounds. The term $\epsilon_{\text{disc}}$ is the localization loss from shrinking the width too fast between rounds, so it plays the role of the step-size term. $\hat s_r$ and $s_r$ are the estimated and true per-frame relevance. $q_r$ is the round-$r$ sampling distribution, the mixture of the blurred relevance map and the evenly spaced share. The minimal-assumption character is that nothing is assumed about where events sit, how relevance varies over time, or how the scorer fails. The only assumption is the minimum event duration. That assumption plays the same role as the early-stopping noise level in A Sharp KL Convergence Analysis for Diffusion Models under Minimal Assumptions: resolution below it is explicitly given up rather than silently lost.
Relation to Prior Work
Two systems motivate the proposal by showing both halves of the trade-off. A.I.R. runs iterative vision-language model scoring and then Localized Density Sampling, which densely resamples frames next to confirmed positive anchors. It gains 7.0 points over uniform sampling on NExT-QA. However, its refinement is greedy, it fails on counting tasks where a single omitted frame is fatal, and it offers no bound on missed intervals. T3S runs many cheap random frame subsets in one batch and averages their logits. It gains 3.1% on LongVideoBench and 8.8% on MLVU Action Order. It is unbiased across the timeline but never focuses its budget on the query.
Our schedule contains both systems as endpoints. With $\lambda = 1$ it is stratified random probing, close to T3S. With $\lambda = 0$ and no annealing it is greedy anchor expansion, close to A.I.R. We add the rule for setting $\lambda$ and the width schedule from the budget and the target certificate length, together with a guarantee that neither endpoint has.
CyberV re-injects frames where attention was lost, using heuristic attention thresholds. Flexible Frame Selection learns a selector with straight-through gradients. Both are scorer-dependent in the same way A.I.R. is, and either could serve as our relevance estimator.
Two further lines of work supply the method. The diffusion convergence literature contributes the smooth-then-refine structure and the average-error accounting; see also Towards Non-Asymptotic Convergence for Diffusion-Based Generative Models. Separately, Test-Time Anchoring for Discrete Diffusion Posterior Sampling fixes high-confidence anchor tokens early to collapse uncertainty in the rest of the sequence. We use anchors the same way, with one change: our anchors never consume the exploration floor.
One result constrains the design. Temporal Backtracking Search shows that early commitment is the dominant failure of test-time search over time. That is precisely the failure the floor is meant to prevent, and it argues against pure Best-of-N over full passes.
Finally, More Thinking, Less Seeing? and SPORTU report that longer reasoning chains in multimodal models drift away from visual evidence and can lower accuracy. This motivates a secondary question: does a marginal unit of test-time compute buy more when spent on frames than when spent on reasoning tokens?
Research Program
The method runs over $R$ rounds, with a typical $R$ of 3 to 4. Each round draws $k$ frames, and those frames come from two sources. A fraction $\lambda$ are evenly spaced with a random offset. The rest are drawn from the current relevance map after convolving it with a kernel of width $h_r$. The width starts near $T/k$ and shrinks geometrically toward the target resolution $w$.
The relevance map is updated after each round from the scorer. We use two scorers so the result is not tied to one estimator: a cheap CLIP similarity scorer and the 1–5 vision-language model ratings from A.I.R. Frames from all rounds are pooled, and the final answer comes from a frozen video model, Qwen2.5-VL-7B and InternVL3-8B, as in CyberV's evaluation.
On the analysis side, we will prove the coverage statement, which is elementary, and the average-error bound. The second proof requires a monotonicity condition on how the answer model uses evidence frames, and we will state that condition explicitly rather than hide it. From the bound we will derive a closed-form choice of $\lambda$ and the width schedule given $k$, $R$, and $w$. We will then test whether this derived setting matches or beats per-benchmark tuning.
Baselines
The naive reference is uniform sampling at the same total frame count, which every selection paper compares against.
The training-free multi-rate baseline is SlowFast-LLaVA. It combines a few high-resolution frames with many pooled frames, and it reports beating IG-VLM by 11.4% on EgoSchema, though the file gives no absolute accuracy. It is strong because it spends nothing on selection. We run it at a matched total visual-token count.
The cheap adaptive baseline is CLIP top-K selection with no exploration share.
The query-agnostic test-time scaling baseline is T3S. We run it with the same number of answer-model forward tokens and the same trial count $R$.
The strongest competitor is A.I.R., since it is the best-documented adaptive selector in the file. On NExT-QA it reports +7.0 points absolute over uniform sampling with Qwen2.5-VL, and on Video-MME it reports 42.3s latency versus 162.0s for direct analysis. No reported Video-MME accuracy for A.I.R. was found on Lacuna, and no reported LongVideoBench or MLVU result for A.I.R. was found on Lacuna. For context, Flexible Frame Selection reports 62.2% versus 61.6% at a 13.5x FLOP reduction on NExT-QA.
All methods share the answer model, the scorer where applicable, the total frames shown to the answer model, and the count of scorer calls. Wall-clock time is reported alongside. A.I.R.'s hyperparameters keep their published values. Our $\lambda$ and widths come from the derived rule, with no per-benchmark tuning.
We count it as beating A.I.R. if two conditions hold together: we match its NExT-QA gain within noise, and we significantly exceed it on the long-certificate and transient-event subsets described below. A gap opening on those subsets is what the coverage argument predicts.
Three ablations isolate the ingredients. The first sets $\lambda = 0$, keeping annealing but dropping the floor. The second uses a fixed width with no annealing. The third replaces the stratified floor with independent random frames, which tests whether stratification rather than randomness provides the guarantee.
Why not just…?
Why not just use SlowFast-style multi-rate sampling and skip selection entirely? Its fast pathway is still uniform downsampling. Its authors note it misses transient actions and fine timestamps, and SPORTU shows that rule violations are undetectable when the decisive frame is skipped, even with slow-motion footage. Our SPORTU foul-detection split, where GPT-4o scores 57.8%, is the direct test. If SlowFast ties us there at matched tokens, our approach has no advantage in the regime it targets.
Why not just run T3S with more trials? Random probing gets the coverage property only in expectation. It needs memory linear in the trial count and never concentrates frames where the query points. Our floor provides deterministic coverage with a fraction of the budget and frees the rest for focusing. The matched-token comparison on LongVideoBench and MLVU decides this. If T3S equals us at every budget, the adaptive share is not earning its cost.
Why not just add a few uniform frames to A.I.R. and tune the fraction? This is the real threat, because hand-mixing is close to our $\lambda > 0$ endpoint. Our claim is narrower than "mixing helps." We claim that the derived $\lambda$ and width schedule transfer across benchmarks and budgets without tuning, and that annealing adds to the floor. We will include A.I.R. plus a tuned uniform fraction, tuned per benchmark on held-out splits, as an extra baseline. If it matches our untuned rule everywhere, the contribution reduces to the guarantee and the explanation of why mixing works, and we will report it that way.
Why not just spend the extra compute on longer reasoning? Both RH-Bench and SPORTU show that longer reasoning chains can reduce perceptual accuracy in multimodal models. We test this directly by matching added FLOPs between extra frames and extra chain-of-thought tokens.
Proposed Experiments
The decisive check is a synthetic needle study built by splicing short query-relevant clips of controlled duration $w$ into long distractor videos. A deliberately adversarial scorer ranks the needle below all distractors. The theory predicts recall equal to 1 whenever $w \ge T/(\lambda k)$, regardless of the scorer. Under the same conditions, A.I.R. and CLIP top-K should collapse toward zero. Recall is the fraction of trials in which the needle is shown to the answer model.
On real data we evaluate NExT-QA, EgoSchema, the long split of Video-MME, LongVideoBench, MLVU, and SPORTU-video. We report accuracy against frame budget from 8 to 64 frames, and we split results by evidence duration. For that split we annotate certificate length on a sample in the way EgoSchema defines it, and we use the Hard foul tasks in SPORTU as the transient regime.
The predicted signature has four parts. We should tie A.I.R. on short-certificate questions and beat it on transient and long-certificate ones. We should beat T3S at low budgets, where focusing matters most. The ablation with $\lambda = 0$ should reproduce A.I.R.'s failure cases. Finally, the measured miss rate should track the bound's scorer-error term once that term is estimated on annotated frames.
A secondary experiment holds total FLOPs fixed and sweeps the split between frames and reasoning tokens on VideoMMMU and Video-MME. It tests whether perceptual compute dominates reasoning compute for video questions.
References
- Sampling is as easy as learning the score: theory for diffusion models with minimal data assumptions
- EgoSchema: A Diagnostic Benchmark for Very Long-form Video Language Understanding
- A Sharp KL Convergence Analysis for Diffusion Models under Minimal Assumptions
- A.I.R.: Enabling Adaptive, Iterative, and Reasoning-based Frame Selection For Video Question Answering
- Test-Time Temporal Sampling for Efficient MLLM Video Understanding
- CyberV: Cybernetics for Test-time Scaling in Video Understanding
- Flexible Frame Selection for Efficient Video Reasoning
- Towards Non-Asymptotic Convergence for Diffusion-Based Generative Models
- Test-Time Anchoring for Discrete Diffusion Posterior Sampling
- Temporal Backtracking Search for Test-time Generative Video Reasoning
- More Thinking, Less Seeing? Assessing Amplified Hallucination in Multimodal Reasoning Models
- SPORTU: A Comprehensive Sports Understanding Benchmark for Multimodal Large Language Models
- SlowFast-LLaVA: A strong training-free baseline for video large language models