Choosing Video Frames as Discrete Sets with Unbiased Gradients

Video question-answering models cannot look at every frame. A one-hour clip at 30 frames per second has more than 100,000 frames, so systems keep a few dozen evenly spaced ones and hope the answer lies among them. For questions such as "did the player step out of bounds before passing?", the decisive moment often lasts a fraction of a second and falls between the kept frames. We propose to train a small frame selector that reads the question and a cheap low-resolution preview of the video, then picks which frames the large model will actually see and how many it needs. The selector learns from one signal only: whether the frozen video model answers correctly with those frames.

Picking frames is a discrete choice. The usual way to train discrete choices by gradient descent is to blend options softly, but blending video frames produces averaged images the answering model never sees at test time. We instead treat each selection as an unordered set of distinct frames, drawn without replacement. We train it with the unbiased, low-variance gradient estimators developed for discrete latent variables, and we borrow the "spend only as much as the query needs" budgeting rule from adaptive sparse attention in language models. The claim is that this combination gives better accuracy per frame than training-free similarity-based selection, and better accuracy than soft-relaxation training, on benchmarks where the decisive events are brief.

Core Claim

A query-conditioned frame selector should beat both uniform sampling and training-free query–frame similarity ranking at equal frame budgets on transient-event video benchmarks, under two conditions. First, it is trained as a distribution over unordered frame subsets. Second, it uses a without-replacement score-function estimator with a built-in leave-one-out baseline. We further claim that soft relaxations (Gumbel-Softmax over frames, or straight-through top-$k$) do measurably worse at the same compute, because of the mismatch between training and test inputs. Finally, letting the selector choose its own budget per query, in the spirit of cumulative-mass pruning, lowers average frame count without hurting accuracy.

Where the Directions Meet

The problem comes from the sparse-temporal-sampling literature. SlowFast-LLaVA builds a training-free video model on uniformly sampled frames and documents the bias that uniform spacing creates. SPORTU shows that rule-based sports questions become unanswerable when the frame holding the key event is skipped. UAL-Bench shows that sparse uniform sampling is an information bottleneck for localizing unusual activities. These papers establish the gap; none of them learns which frames to keep.

The selection structure comes from adaptive attention sparsity, where the same question is posed over tokens rather than frames. QUEST shows that importance is a property of the query–token pair, not of the token alone. It keeps 100% passkey-retrieval accuracy at a 1% token budget, while query-agnostic eviction collapses to 0–4%. We take from it the argument that frame importance must be query-conditioned.

Twilight keeps entries until a fixed share of cumulative attention mass is covered, so the budget grows or shrinks with the input. TidalDecode argues that fixed budgets waste compute on easy inputs and starve hard ones. These two motivate our adaptive budget.

Learned selectors in this literature tell us what to avoid. SeerAttention trains block gates by self-distillation against dense attention. That signal does not exist for frames that were never encoded. Attention with Routed-Memory uses Gumbel-Softmax slot selection plus a policy trained as a decision process. That is the relaxation route we argue against.

The training method comes from discrete gradient estimation. Estimating Gradients for Discrete Random Variables by Sampling without Replacement draws distinct samples with the Gumbel-top-$k$ trick. It Rao-Blackwellizes over orderings, meaning it averages out the arbitrary draw order exactly, and includes a leave-one-out control variate that costs no extra function evaluations. The file lists that estimator's weakness as treating structured outputs as flat sets. Frame selection is the case where that weakness disappears, because a frame subset really is an unordered set: temporal order is restored from timestamps before the frames reach the answering model.

ARSM gives an unbiased estimator for many-way categorical choices. REBAR builds a control variate from a relaxation while staying unbiased. Both are comparison estimators. Feature Selection using Stochastic Gates and Discrete Variational Autoencoders document the bias that continuous relaxations introduce. These constrain our design: they are why we do not relax.

The research file was cut off before its section on prior overlap. We therefore could not check whether a reward-trained, without-replacement frame selector already exists. This is the first thing to verify before committing compute.

Research Program

The selector is a light network. It scores $T$ candidate frames from cheap features, such as a low-resolution visual encoder pass and the question embedding. Its output defines a Plackett–Luce distribution $q_\theta$ over frames, which describes drawing frames one at a time without replacement in proportion to their scores. A subset $S$ of size $m$ is drawn by perturbing the scores with Gumbel noise and keeping the top $m$.

The frozen video model then answers from the frames in $S$, placed in temporal order. It returns a reward $f(S)$, defined as the log-likelihood of the correct answer (or of the correct temporal span for localization) minus a cost $\lambda m$. The training objective is

$$\max_\theta \; \mathbb{E}_{S \sim q_\theta}\big[f(S)\big],$$

with gradient $\mathbb{E}[f(S)\,\nabla_\theta \log q_\theta(S)]$. Here $q_\theta(S)$ is the probability of the unordered set, summed over all orderings in which $S$ could have been drawn.

Per training example, we draw $n$ independent subsets (we plan $n=4$). For each, we subtract the mean reward of the other $n-1$ subsets as a baseline, which keeps the estimate unbiased. We compute $\log q_\theta(S)$ with the numerical-integration approach from the without-replacement estimator paper. This is the main engineering risk, since that paper's own limitations note its combinatorial cost. The fallback is the ordered-sample log-probability, which is cheap and still unbiased but noisier. Comparing the two is an explicit ablation.

The budget is a separate categorical choice $m \in \{4, 8, 16, 32\}$, predicted from the question and the preview and trained with the same reward. ARSM serves as the alternative estimator for this small choice. The cost $\lambda$ traces out an accuracy-versus-frames curve, playing the role of Twilight's mass threshold.

We also measure gradient variance directly: we compute repeated gradient estimates at fixed parameters and report their variance per estimator. This lets us check whether claimed variance gains carry over from MNIST variational autoencoders to this task.

Baselines

The naive reference is uniform sampling at the same frame count, run through the same frozen model exactly as in SlowFast-LLaVA's setup. The file reports no SPORTU or UAL-Bench number for that system ("no reported result found on Lacuna for SlowFast-LLaVA on SPORTU or UAL-Bench"), so we will reproduce it. Beating it means higher SPORTU accuracy and higher UAL-Bench localization recall at matched average frames.

The strongest training-free competitor is query–frame similarity ranking. It scores each preview frame against the question embedding and keeps the top $m$, using the same preview features as our selector, so input information is identical. This is the QUEST idea transplanted to frames, and it is the baseline most likely to match us.

The strongest learned competitor is the same selector architecture trained with Gumbel-Softmax soft frame mixing and with straight-through top-$k$. Both get the same training data, the same number of frozen-model forward passes, and a temperature sweep of equal size to our tuning budget. The file reports no frame-selection number for this either. On categorical variational autoencoders, ARSM reports test negative ELBO of 86.7 against 95.9 for Gumbel-Softmax (ARSM). That is evidence the gap exists elsewhere, not proof that it appears here.

An upper reference encodes all frames densely and lets QUEST-style page selection run inside the language model. This shows what a much larger encoding budget buys.

Three ablations isolate the key ingredients. Plain single-sample REINFORCE with a moving-average baseline tests whether the without-replacement estimator matters. Ordered versus unordered log-probability tests whether the Rao-Blackwellization over orderings is worth its cost. Fixed $m$ versus learned $m$ tests the adaptive budget.

Why not just…?

Why not just rank frames by similarity to the question? This is the real threat. Many questions name a visible object, and text–image similarity will find it. Similarity fails when relevance is relational or temporal ("before passing", "after the foul"), or when the decisive frame resembles many others. That is the kind of failure SPORTU and UAL-Bench were built to expose. We will split results by question type. If similarity matches us on relational and temporal questions too, the learned selector is not worth training, and we will report that.

Why not just use Gumbel-Softmax and backpropagate through the answering model? A soft mixture of frames is a blended image. The frozen model is trained on clean frames, so the gradients describe behavior on inputs it never receives at test time. The relaxation literature cited above documents exactly this train–test bias. The matched-compute comparison tests whether it matters at our scale.

Why not just sample more frames uniformly? More frames cost encoder compute and context length linearly. At any fixed budget, the gaps between kept frames remain. We report accuracy against frame count for uniform sampling up to the context limit. If uniform sampling at 2× frames matches our selector, the selector's value is reduced to the compute saved, and we report it on those terms.

Proposed Experiments

We freeze one open video language model of the SlowFast-LLaVA family. We train on video-disjoint splits of SPORTU and UAL-Bench; we define these splits ourselves where the benchmarks do not and publish them. We evaluate SPORTU by multiple-choice accuracy and UAL-Bench by localization recall at standard overlap thresholds. Alongside accuracy, we report average frames used, encoder FLOPs, and wall-clock time including the preview pass, so the selector's own overhead is counted.

The decisive check is the accuracy-versus-average-frames curve against similarity ranking, restricted to temporal and relational questions. The proposal stands only if our curve lies above it there. Two secondary checks follow. The measured gradient variance of the without-replacement estimator should be lower than plain REINFORCE and should come with faster reward improvement. The learned budget should use fewer frames on single-object factual questions than on ordering questions.