A Parameter-free Scene Detection Algorithm for Vision and Language Understanding

Louis Mahon, Mirella LapataSubmission to ICLR 2026 · Withdrawn

TL;DR

Processing full-length movies with end-to-end vision-language models is computationally prohibitive due to context and memory limits. This paper introduces MDLSeg, an entirely parameter-free video scene segmentation algorithm rooted in the Minimum Description Length (MDL) principle and solved efficiently with dynamic programming. MDLSeg outperforms both heuristic cut-detectors and supervised deep models on scene boundary detection, while significantly boosting downstream movie summarization and long-form video question answering (QA).

What Problem Does This Paper Address?

End-to-end Large Vision-Language Models (LVLMs) struggle to consume full-length films: processing a 75-minute movie at modest resolutions can easily demand over 500 GB of memory as raw tensors. Modular systems—which break a video into manageable chunks, caption them, and reason over them hierarchically—offer a practical alternative.

However, deciding where to split a video is non-trivial. Heuristic tools like PySceneDetect rely on frame-difference thresholds that trigger false breaks during internal shot changes (e.g., cutting back and forth between two talking characters). Meanwhile, modern deep learning segmenters require supervised training and often fail to generalize across genres, and clustering baselines like $k$-means require manually specifying the target number of scenes ($k$).

Methods

The authors frame scene segmentation as a contiguous clustering problem and resolve the classic trade-off between cluster tightness and cluster count using information theory:

  • Minimum Description Length (MDL) Objective: Rather than relying on arbitrary loss functions or similarity thresholds, MDLSeg measures the total bits required to transmit the video's frame features (extracted via CLIP). Each scene is modeled as a multivariate Gaussian parameterized by its mean and diagonal covariance. The cost to represent the parameters takes $2dm$ bits (where $d$ is feature dimensionality and $m$ is floating-point precision), while encoding each frame feature $v$ requires $-\log_2 p(v)$ bits by the Kraft-McMillan inequality. Minimizing total description length naturally penalizes having too many scene parameters while favoring tight clusters.
  • Dynamic Programming Search: Because scenes must be temporally contiguous, the global minimum bit-cost can be calculated exactly via dynamic programming: $$C(i, j) = \min_{i+1 \le k \le j} [B(i, k) + C(k, j)]$$ By bounding the maximum plausible scene length to $L$ (e.g., ~10 minutes, or 300 keyframes), complexity drops from $O(N^2)$ to $O(N)$, executing in mere seconds for a full movie.

  • Modular Downstream Pipelines:

  • Long Video Summarization: Uses WhisperX for diarized transcripts, extracts actor faces from IMDb to assign character names to speaker IDs via the Hungarian algorithm (bipartite matching), captions keyframes with Llava-NeXT, and produces hierarchical summaries with Llama-3.1 70B.
  • Video QA (RAG): Uses MDLSeg chunks to retrieve relevant video/transcript segments matching a query before passing context to an LLM.

Datasets

  • Direct Scene Detection: Evaluated on OVSD (16 diverse online films, 10–90 min) and BBC Earth (11 50-minute Planet Earth episodes with annotations from 5 different humans).
  • Downstream Summarization: Evaluated on MovieSum across 175 full-length movies (averaging 118 minutes and 151 screenplay scenes each).
  • Downstream Video QA: Evaluated on TVQA-long, spanning 924 episodes across six TV series (e.g., Friends, House, Castle).

Key Insights and Ideas

  • Principled unification of cut vs. stay: Standard clustering methods struggle to balance "points should be close to centroids" against "don't create too many clusters" because the two penalties use incompatible scales. MDL unifies both terms into a single, concrete currency: bits.
  • Contiguity makes exact optimization tractable: While general MDL clustering is NP-hard, strict temporal contiguity allows exact global optimization via 1D dynamic programming.
  • Better scenes directly yield better LLM reasoning: When retrieving context for QA, heuristic cuts (like PySceneDetect) fragment scenes into 10–15 second snippets that lose conversational context. Uniform 3-minute splitting works decently on sitcoms only because of hard-coded genre priors, whereas MDLSeg adapts to pacing across genres without tuning.
  • Evaluating zero-shot LVLMs faces severe contamination: When the authors removed video input entirely on TVQA-long, models like Qwen-VL and LLaVA-OneVision still scored ~35–37% on 5-way multiple-choice questions (chance is 20%), highlighting pervasive training data contamination in existing multimodal benchmarks.

Key Results

  • Scene Boundary Detection: On OVSD, MDLSeg achieves 63.37% cluster accuracy, 72.58 NMI, and a WindowDiff error of 42.58, outperforming PySceneDetect (47.35% acc; 155.77 WindowDiff) and supervised deep models like HEM (61.20% acc) and NeighborNet (59.40% acc).
  • Long Video Summarization: On MovieSum, the MDLSeg hierarchical pipeline reaches 10.32 ROUGE-2 and 53.57 PRISMA score, beating end-to-end models like Otter (3.06 ROUGE-2) and screenplay-based uniform chunking (8.45 ROUGE-2).
  • Long Video QA: On TVQA-long, MDLSeg-driven retrieval reaches 40.92% accuracy, outperforming PySceneDetect chunks (33.68%), uniform chunks (39.99%), and passing full unsegmented transcripts (20.09%).

Limitations and Future Work

  • Reliance on Pre-extracted Visual Features: The algorithm's partitions depend heavily on the semantic quality and geometry of the upstream frame encoder (e.g., CLIP).
  • Cascading Errors in Downstream Pipelines: Although modularity brings transparency and bypasses memory limits, upstream errors in speaker diarization (WhisperX) or face recognition directly cascade into character name misattributions during summarization.
  • Multimodal Boundary Detection: While experiments show vision-only features currently perform best, incorporating audio or dialogue cues into the MDL objective without diluting the visual signal remains an open challenge.

Summary updated

Abstract

The proliferation of creative video content has driven demand for adapting language models to handle video input and enable multimodal understanding. However, end-to-end models struggle to process long videos due to their size and complexity. An effective alternative is to divide them into smaller chunks to be processed separately, and this motivates a method for choosing where the chunk boundaries should be. In this paper, we propose an algorithm for segmenting videos into contiguous chunks, based on the minimum description length principle, coupled with a dynamic programming search. The algorithm is entirely parameter-free, given feature vectors, not requiring a set threshold or the number or size of chunks to be specified. We show empirically that the breakpoints it produces more accurately approximate scene boundaries in long videos, compared with existing methods for scene detection, even when such methods have access to the true number of scenes. We then showcase this algorithm in two tasks: long video summarization, and retrieval-augmented video question answering. In both cases, scene breaks produced by our algorithm lead to better downstream performance than existing methods for video segmentation.
BibTeX
@misc{mahon2025parameter,
  author = {Louis Mahon and Mirella Lapata},
  title = {{A Parameter-free Scene Detection Algorithm for Vision and Language Understanding}},
  year = {2025},
  eprint = {2503.01201},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2503.01201},
}
Figure