Video Summary Evaluation That Does Not Depend on Vocabulary Size

Video summarization benchmarks are tiny. SumMe has 25 videos and TVSum has 50. On these benchmarks a completely random summary scores an F1 of 0.57 on TVSum, which beats several published deep models, and 0.41 on SumMe, close to the 0.54 agreement between two humans (Rethinking the Evaluation of Video Summaries). Information-based scores look like a natural fix: a good summary should let you reconstruct, or cheaply describe, the rest of the video. But they inherit a hidden choice. To count "how much of the video's content the summary contains," frames must be turned into discrete symbols, such as clusters of visual features, and nothing about video fixes how many clusters to use. With a few hundred shots per video and an open-ended space of scenes, any finite vocabulary is either too coarse or too sparse. A naive code-length score then drifts with that arbitrary vocabulary size.

This note proposes a summary score built from universal compression over infinite alphabets. Universal compression is the theory of coding data from an unknown source, where the alphabet is unbounded but symbol frequencies are assumed to fall off under a known curve, the "envelope." The score is computed with Poissonization: the trick of treating the sequence length as random, which makes the counts of different symbols statistically independent. The score is the number of bits needed to describe the full video once the summary is known. We use a code whose excess cost is provably finite however fine the visual vocabulary gets. Poissonization also splits the score into independent per-symbol terms, which gives exact variances and confidence intervals at benchmark sizes of 25 to 50 videos. The claim to test is simple. Such a score ranks human summaries above random and above segment-length-gamed summaries, and its rankings stay stable across a 64-fold range of vocabulary sizes. Finite-alphabet and plug-in scores fail at least one of these.

Core Claim

Represent each video as a frame-level sequence of shot codewords. Each frame inherits the cluster label of its shot, at granularity $k$. A summary $S$ is scored by the conditional description length $L(V \mid S)$: the bits a sequential code needs to encode the label-free pattern of video $V$ after first being shown the summary's frames. A pattern is the order in which new symbols first appear, so that "banana" becomes 123232. The score is normalized by the unconditioned length $L(V)$, and lower is better. Coding at the frame level means long scenes carry proportionally more mass. A summary that grabs many short shots, which is the behaviour the 15% budget knapsack step rewards in Otani et al.'s analysis, gains little unless it also covers the scenes that dominate the video's duration. Coding patterns rather than labels makes the score invariant to how clusters are numbered. Using an envelope-class code makes the excess cost over the ideal bounded as $k$ grows. We assume symbol probabilities sorted in decreasing order satisfy $p_i \le c\, i^{-\alpha}$ with $\alpha > 1$.

Under Poisson sampling the expected score separates:

$$\mathbb{E}\,L(V \mid S) \;=\; \sum_{j} \ell\big(\lambda_j,\, m_j\big) \;+\; O(1),$$

Here $j$ ranges over codewords, $\lambda_j$ is the Poisson rate of codeword $j$ in the video, $m_j$ is its count in the summary, $\ell$ is the single-letter coding cost of a Poisson count given that side information, and the $O(1)$ is the roughly one-bit gap between Poisson and fixed-length redundancy. That decomposition, and the one-bit bridge back to fixed-length sequences, come from Tight bounds for universal compression of large alphabets. and Universal Compression of Envelope Classes: Tight Characterization via Poisson Sampling. They proved it for unconditional minimax redundancy. We need the conditional, side-information version, which is the theoretical piece of this work. Because the terms are independent, the score's variance is a sum of per-codeword variances. That sum yields a per-video confidence interval without bootstrapping over a handful of videos.

Research Program

The work has three parts. The first is analytic. We extend the Poisson single-letter decomposition to coding with side information, and bound how the conditional redundancy depends on $k$ under a power-law envelope. The target is a statement that the score changes by $O(\log n)$ bits or less as $k$ ranges from 64 to 4096, where $n$ is the number of frames. By contrast, a finite-alphabet code pays about $\frac{k-1}{2}\log n$ bits, so its score moves linearly with $k$. We use Jennifer Tang's pattern regret bound $c\,n^{1/3}(\log n)^{4/3}$ (Minimax Regret on Patterns Using Kullback-Leibler Divergence Covering) as the worst-case cap for the pattern component.

The second part is a working sequential encoder. The papers above prove existence through Shtarkov sums and coverings and give no implementable code, which is the gap listed under algorithmic implementability. We build an online pattern coder with an escape mechanism for unseen symbols. Its per-symbol cost is set by the Poissonized single-letter terms, with the envelope parameters $(c, \alpha)$ either fixed or chosen by a two-part code. We then check empirically that its regret on synthetic power-law sources tracks the theoretical bound.

The third part is the evaluation study on video, described below.

One honest limitation shapes the design. The theory assumes independent and identically distributed draws, while video frames are strongly dependent in time. Frame-level labels within a shot are deterministic copies, so the effective source is the shot sequence weighted by duration. We treat the shot sequence as the unit and report how far the observed variance departs from the Poisson prediction. That gap is itself a measurement of how much temporal dependence the method ignores. Tang explicitly leaves Markov sources open, and we do not claim to solve that.

Baselines

The naive reference is the random summary under Otani et al.'s randomization protocol: uniform random importance scores passed through Kernel Temporal Segmentation (KTS, the standard change-point shot segmenter) and the 15% knapsack step. It reaches F1 0.57 on TVSum and 0.41 on SumMe (Rethinking the Evaluation of Video Summaries). We add uniform-interval sampling, and two length-gamed variants: random summaries built only from the shortest shots, and random summaries built only from the longest shots, all at the same 15% budget. Every candidate score must rank the human summaries above all of these. TVSum provides 20 human annotations per video, and SumMe provides 15 to 20 human summaries.

The strongest existing evaluation method is Otani et al.'s rank correlation (Kendall's $\tau$ and Spearman's $\rho$) between predicted and human frame importance. That paper reports $\rho = 0.055$ for dppLSTM against $0.000$ for random on TVSum. We compute it on the same videos and the same summaries. Because rank correlation scores importance curves rather than selected subsets, we compare the two scores on their shared task: separating human subsets from random and gamed ones, and ranking published models consistently. To beat it, the proposed score must give a larger standardized gap between human and random summaries, and a model ranking that is more stable across the five cross-validation splits.

The strongest information-based competitor is TRIM's representativeness term, the Wasserstein-2 distance between the feature distributions of summary frames and video frames (TRIM: A Self-Supervised Video Summarization Framework Maximizing Temporal Relative Information and Representativeness). We implement it on the same frozen frame features. TRIM reports state-of-the-art unsupervised F1 and 3.27 GFLOPs. No reported result found on Lacuna for Wasserstein-2 as a standalone evaluation score.

Two ablations isolate the key ingredient. The first replaces the envelope pattern code with a fixed-$k$ finite-alphabet adaptive code, which tests whether the infinite-alphabet treatment matters. The second replaces it with plug-in empirical entropy of codeword frequencies, which tests whether a coding guarantee matters at all. All scores use the same features, the same KTS shots, the same $k$ grid, and no tuning on test videos. The envelope parameters are fit only on held-out training-fold videos.

Why not just…?

Why not just use rank correlation, as Otani et al. recommend? For scoring importance curves, rank correlation remains the right tool, and we keep it. It cannot score what systems actually output, which is a discrete subset under a length budget. Otani et al. themselves note that it says nothing about coverage or redundancy. If the proposed score adds no separating power beyond $\tau$ and $\rho$ on human-versus-random subsets, the proposal has failed. The first experiment checks exactly that.

Why not just use a continuous distance such as TRIM's Wasserstein-2 and avoid alphabets altogether? This is a real threat, because Wasserstein-2 needs no vocabulary choice. Its weaknesses are different. It is estimated from a few hundred high-dimensional frames per summary, where empirical transport distances are badly biased, and it gives no per-video uncertainty. Whether those weaknesses matter in practice is an empirical question. We settle it by comparing human-versus-random separation and cross-split stability head to head. We also test robustness to feature dimension by projecting features to 32, 128, and 512 dimensions. If Wasserstein-2 matches the proposed score, we will report that the simpler continuous score suffices.

Why not just fix a vocabulary size and use a standard finite-alphabet code, or bootstrap for error bars? The finite code is the first ablation. Its excess cost grows with $k$, so we expect its model rankings to change as the clustering is refined, and the $k$-sweep tests this directly. Bootstrapping over 25 to 50 videos is possible but coarse. The Poisson decomposition gives analytic per-video intervals, and we validate them against the bootstrap rather than assume they are correct.

Proposed Experiments

The main study runs on TVSum and SumMe with standard 5-fold splits. It uses frozen frame features and KTS shots, with codewords clustered at $k \in \{64, 256, 1024, 4096\}$. We score human summaries, the random and length-gamed baselines, and the outputs of re-run published models: dppLSTM, SUM-GAN-AED (which reports F-score 63.18% on TVSum and 64.85% on SumMe, per Self-Attention Based Generative Adversarial Networks For Unsupervised Video Summarization), TRIM, and SpiVG (F1 53.7 on SumMe, per Spiking Variational Graph Representation Inference for Video Summarization).

Three checks decide the outcome. First, human summaries must beat random and both length-gamed variants under the proposed score on at least 90% of videos, a bar F1 visibly fails. Second, the Kendall agreement of model rankings between $k=64$ and $k=4096$ should exceed that of the finite-alphabet and plug-in ablations. Third, the analytic Poisson intervals should cover the bootstrap estimate. Where they do not, the shortfall quantifies the temporal dependence the method ignores.

A synthetic sanity study comes first. We draw sequences from known power-law sources with $\alpha \in \{1.2, 1.5, 2\}$ and check that the encoder's measured regret stays under the Tang and Acharya bounds at $n$ from $10^2$ to $10^4$, which are benchmark-scale frame counts. As a scale check, we run on Mr. HiSum (31,000 videos with viewer-derived importance; no reported result found on Lacuna for its metrics). There we ask whether the score's ranking of models on random 50-video subsets agrees with its ranking on the full set. A score built for small benchmarks should show that agreement, and F1 should show less of it.